<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  
  <title itemprop="name">动态规划刷题整理 | 楓の葉小窝</title>
  
    <link rel="shortcut icon" href="/images/favicon.ico">
  
  <meta http-equiv="x-dns-prefetch-control" content="on">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Noto+SerifMerriweather|Merriweather+Sans|Source+Code+Pro|Ubuntu:400,700|Noto+Serif+SC" media="all">
  <link rel="dns-prefetch" href="//cdn.jsdelivr.net">
  <link rel="stylesheet" id="saukra_css-css" href="/css/style.css" type="text/css" media="all">
  <link rel="stylesheet" href="/css/lib.min.css" media="all">
  <link rel="stylesheet" href="/css/font.css" media="all">
  <link rel="stylesheet" href="/css/insight.css" media="all">
  <link rel="stylesheet" href="/css/jquery.fancybox.min.css" media="all">
  <link rel="stylesheet" href="/css/zoom.css" media="all">
  <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<!--   <link rel="stylesheet" id="saukra_css-css" href="https://2heng.xin/wp-content/cache/autoptimize/css/autoptimize_ad42a61f4c7d4bdd9f91afcff6b5dda5.css
" type="text/css" media="all"> -->
  <script>
  /*Initial Variables*/
  var mashiro_option = new Object();
  var mashiro_global = new Object();
  mashiro_option.NProgressON = true;
  /* 
   * 邮箱信息之类的东西可以填在这里，这些js变量基本都作用于sakura-app.js
   * 这样的设置仅是为了方便在基于PHP开发的主题中设置js变量，既然移植到了Node上，我想或许可以精简这一逻辑吧
   */
  mashiro_option.email_domain = "";
  mashiro_option.email_name = "";
  mashiro_option.cookie_version_control = "";
  mashiro_option.qzone_autocomplete = false;
  mashiro_option.site_name = "楓の葉lean";
  mashiro_option.author_name = "lean";
  mashiro_option.site_url = "https://linxuesong.github.io";
  mashiro_option.v_appId = "RmgA0rMeKIWWIkhSTpqhV4oG-gzGzoHsz";
  mashiro_option.v_appKey = "iwivlkfT6bGJRQS74SaKYjal";
  mashiro_option.mathjax = "0";
  mashiro_option.qq_api_url = "https://api.mashiro.top/qqinfo/"; 
  mashiro_option.qq_avatar_api_url = "https://api.mashiro.top/qqinfo/";

  // mashiro_option.jsdelivr_css_src = "https://cdn.jsdelivr.net/gh/moezx/cdn@3.4.5/css/lib.min.css";
  // mashiro_option.float_player_on = true;

  /*End of Initial Variables*/
  </script>
  <script type="text/javascript">
  var bg = "https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(1).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(2).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(3).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(4).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(5).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(1).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(2).jpg,https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/backgroundCover/cover(3).jpg".split(",");
  var bgindex = Math.floor(Math.random()*bg.length);
  if (!!window.ActiveXObject || "ActiveXObject" in window) { //is IE?
    alert('朋友，IE浏览器未适配哦~');
  }
  </script>
  <style type="text/css">
  .hljs-ln{border-collapse:collapse}.hljs-ln td{padding:0}.hljs-ln-n:before{content:attr(data-line-number)}
  </style>
  <style type="text/css">.site-top .lower nav{display:block !important;}.author-profile i,.post-like a,.post-share .show-share,.sub-text,.we-info a,span.sitename,.post-more i:hover,#pagination a:hover,.post-content a:hover,.float-content i:hover{color:#FE9600}.feature i,.download,.navigator i:hover,.links ul li:before,.ar-time i,span.ar-circle,.object,.comment .comment-reply-link,.siren-checkbox-radio:checked + .siren-checkbox-radioInput:after{background:#FE9600}::-webkit-scrollbar-thumb{background:#FE9600}.download,.navigator i:hover,.link-title,.links ul li:hover,#pagination a:hover,.comment-respond input[type='submit']:hover{border-color:#FE9600}.entry-content a:hover,.site-info a:hover,.comment h4 a,#comments-navi a.prev,#comments-navi a.next,.comment h4 a:hover,.site-top ul li a:hover,.entry-title a:hover,#archives-temp h3,span.page-numbers.current,.sorry li a:hover,.site-title a:hover,i.iconfont.js-toggle-search.iconsearch:hover,.comment-respond input[type='submit']:hover{color:#FE9600}.comments .comments-main{display:block !important;}.comments .comments-hidden{display:none !important;}background-position:center center;background-attachment:inherit;}
  </style>
  
  
  <!--标签统计样式-->
  <link rel="stylesheet" href="/css/tags.css" media="all">

  <!--百度访问数据统计-->
  <script>
  var _hmt = _hmt || [];
  (function() {
    var hm = document.createElement("script");
    hm.src = "https://hm.baidu.com/hm.js?d67a00154871861401ec8c26b0bdaf5d";
    var s = document.getElementsByTagName("script")[0]; 
    s.parentNode.insertBefore(hm, s);
  })();
  </script>



<meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="楓の葉小窝" type="application/atom+xml">
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css"></head>

<body class="page-template page-template-user page-template-page-analytics page-template-userpage-analytics-php page page-id-1297 chinese-font serif isWebKit">
  <div class="scrollbar" id="bar">
  </div>
  <a href="#" class="cd-top faa-float animated"></a>
  <section id="main-container">
    <div class="headertop filter-dot">
  <div id="banner_wave_1"></div>
  <div id="banner_wave_2"></div>
  <figure id="centerbg" class="centerbg">
    <div class="focusinfo no-select">
      <div class="header-tou">
        <a href="https://linxuesong.github.io">
          <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/avatar.jpg">
        </a>
      </div>
      <div class="header-info">
        <p>Live your life with passion! With some drive!</p>
        <div class="top-social_v2">
          <li id="bg-pre">
            <img class="flipx" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
          
            
              
                <li>
                  <a href="http://github.com/linxuesong" target="_blank" class="social-github" title="github">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/github.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://blog.csdn.net/lsxa123" target="_blank" class="social-github" title="csdn">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/csdn.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://www.cnblogs.com/linxuesong/" target="_blank" class="social-github" title="cnblog">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/cnblog.jpg">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://wuzhi.me/" target="_blank" class="social-github" title="wuzhi">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/wuzhi.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://space.bilibili.com/396134239/video" target="_blank" class="social-github" title="bilibili">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/bilibili.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://photo.weibo.com/6504280642/wbphotos/large/mid/4519020298017277/pid/0076biwily1gg2bf3v9wvj30f00kk75n" target="_blank" class="social-github" title="qq">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/qq.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://photo.weibo.com/6504280642/wbphotos/large/mid/4519020298017277/pid/0076biwily1gg2bf3v9wvj30f00kk75n" target="_blank" class="social-github" title="wechat">
                    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/social/wechat.png">
                  </a>
                </li>
              
            
          
          <li id="bg-next">
            <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
        </div>
      </div>
    </div>
  </figure>
  <div id="video-container" style="">
    <video style="object-fit: fill" id="bgvideo" class="video" video-name="" src="" width="auto" preload="auto">
    </video>
    <div id="video-btn" class="loadvideo videolive">
    </div>
    <div id="video-add">
    </div>
    <div class="video-stu">
    </div>
  </div>
  <div class="headertop-down faa-float animated" onclick="headertop_down()">
    <span>
      <i class="fa fa-chevron-down" aria-hidden="true">
      </i>
    </span>
  </div>
</div>
    <div id="page" class="site wrapper">
      <header class="site-header no-select gizle sabit" role="banner">
  <div class="site-top">
    <div class="site-branding">
      <span class="site-title">
        <span class="logolink moe-mashiro">
          <a href="/">
            <span class="sakurasono">楓の葉</span>
            <span class="shironeko">lean</span>
          </a>
        </span>
      </span>
    </div>
    <div class="searchbox search-form-submit">
      <i class="iconfont js-toggle-search iconsearch icon-search">
      </i>
    </div>
    <div id="show-nav" class="showNav mobile-fit">
      <div class="line line1">
      </div>
      <div class="line line2">
      </div>
      <div class="line line3">
      </div>
    </div>
    <div class="lower-cantiner">
      <div class="lower">
        <nav class="mobile-fit-control hide">
          <ul id="menu-new" class="menu">
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
                    首页
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
                    归档
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/categories/%E6%8A%80%E6%9C%AF/">
                          <i class="fa fa-laptop" aria-hidden="true"></i>
                          技术
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E7%94%9F%E6%B4%BB/">
                          <i class="fa fa-file-text-o" aria-hidden="true"></i>
                          生活
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%B5%84%E6%BA%90/">
                          <i class="fa fa-cloud-download" aria-hidden="true"></i>
                          资源
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E9%9A%8F%E6%83%B3/">
                          <i class="fa fa-commenting-o" aria-hidden="true"></i>
                          随想
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                          <i class="fa fa-book" aria-hidden="true"></i>
                          转载
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-area-chart faa-vertical" aria-hidden="true"></i>
                    文章统计
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/analytics/">
                          <i class="fa fa-area-chart" aria-hidden="true"></i>
                          统计
                        </a>
                      </li>
                    
                      <li>
                        <a href="/archives/">
                          <i class="fa fa-calendar" aria-hidden="true"></i>
                          日历
                        </a>
                      </li>
                    
                      <li>
                        <a href="/tags/">
                          <i class="fa fa-tag" aria-hidden="true"></i>
                          标签
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/">
                          <i class="fa fa-bookmark" aria-hidden="true"></i>
                          分类
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
                    清单
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/books/">
                          <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                          书单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/bangumi/">
                          <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                          番组
                        </a>
                      </li>
                    
                      <li>
                        <a href="/music/">
                          <i class="fa fa-headphones" aria-hidden="true"></i>
                          歌单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/movies/">
                          <i class="fa fa-video-camera" aria-hidden="true"></i>
                          电影
                        </a>
                      </li>
                    
                      <li>
                        <a href="/games/">
                          <i class="fa fa-gamepad" aria-hidden="true"></i>
                          游戏
                        </a>
                      </li>
                    
                      <li>
                        <a href="/gallery/">
                          <i class="fa fa-photo" aria-hidden="true"></i>
                          图集
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/comment/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
                    留言板
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
                    友人帐
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/links/">
                          <i class="fa fa-handshake-o" aria-hidden="true"></i>
                          小伙伴
                        </a>
                      </li>
                    
                      <li>
                        <a href="/friendlink_status/">
                          <i class="fa fa-heartbeat faa-shake" aria-hidden="true"></i>
                          健康值
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/donate/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
                    赞赏
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
                    关于
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/sourceshare/">
                          <i class="fa fa-share-alt faa-vertical" aria-hidden="true"></i>
                          分享
                        </a>
                      </li>
                    
                      <li>
                        <a href="/sitelog/">
                          <i class="fa fa-calculator" aria-hidden="true"></i>
                          建站史
                        </a>
                      </li>
                    
                      <li>
                        <a href="/todolist">
                          <i class="fa fa-tasks" aria-hidden="true"></i>
                          任务书
                        </a>
                      </li>
                    
                      <li>
                        <a href="/about/">
                          <i class="fa fa-meetup" aria-hidden="true"></i>
                          我？
                        </a>
                      </li>
                    
                      <li>
                        <a href="/theme-sakura/">
                          <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                          主题
                        </a>
                      </li>
                    
                      <li>
                        <a href="/lab/">
                          <i class="fa fa-cogs" aria-hidden="true"></i>
                          Lab
                        </a>
                      </li>
                    
                      <li>
                        <a href="/dinoswords">
                          <i class="fa fa-coffee" aria-hidden="true"></i>
                          娱乐
                        </a>
                      </li>
                    
                      <li>
                        <a href="/client/">
                          <i class="fa fa-android faa-vertical" aria-hidden="true"></i>
                          客户端
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/atom.xml">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
                    RSS
                  </span>
                </a>
                
              </li>
            	
          </ul>
        </nav>
      </div>
    </div>
  </div>
<!-- 和风天气-->
<div id="he-plugin-simple"></div>
<script>
WIDGET = {
  CONFIG: {
    "modules": "30124",
    "background": 4,
    "backgroundColor": "F5A623",
    "tmpColor": "FFFFFF",
    "tmpSize": 16,
    "cityColor": "FFFFFF",
    "citySize": 16,
    "aqiSize": 16,
    "weatherIconSize": "6",
    "alertIconSize": 18,
    "padding": "10px 10px 10px 10px",
    "shadow": "1",
    "language": "auto",
    "borderRadius": 5,
    "fixed": "true",
    "vertical": "bottom",
    "horizontal": "right",
    "right": "0",
    "top": "80",
    "key": "7438089786be4f2984b268f575a35fa8"
  }
}
</script>
<script src="https://widget.qweather.net/simple/static/js/he-simple-common.js?v=2.0"></script>
	<!-- 和风天气-->
</header>

      <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.css">
<div class="pattern-center-blank"></div>

  <div class="pattern-center single-center">
    <!-- 有配图默认渲染第一张 -->
    <img class="pattern-attachment-img lazyload" style="background-image: url(https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/20100G13916-2-1200.jpg);" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/loader/orange.progress-bar-stripe-loader.svg" data-src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/20100G13916-2-1200.jpg">
    </img>
    <header class="pattern-header single-header">
      <h1 class="entry-title">
      动态规划刷题整理</h1>
      <p class="entry-census">
        <span>
          <a href="linxuesong.github.io">
            <img src="https://wx1.sinaimg.cn/large/006bYVyvgy1ftand2qurdj303c03cdfv.jpg">
          </a>
        </span>
        <span>
          <a href="linxuesong.github.io">linxuesong</a>
        </span>
        <span class="bull">
        ·</span>
        2020-12-10<span class="bull">
        ·</span>
      
         	  
	        <!-- 安装插件npm install hexo-wordcount --save -->
			<!--本篇文章浏览访客人数统计 -->   
            <span class="post-meta-item" >
                <span class="post-meta-item-icon">
                    <i class="iconfont icon-attention"></i>
                </span>
			        <span id="busuanzi_value_page_pv"></span>
				<span class="post-meta-item-text">次阅读</span>	
			
            <span class="bull">·</span>
			
			<!--本篇文章文字数统计 -->
            <span class="post-time">
              <span class="post-meta-item-icon">
                <i class="fa fa-book"></i>
                <span class="post-count">9.9k字</span>
              </span>
            </span>
            
			<span class="bull">·</span>
            
            <!-本篇文章预计阅读时间-->			
            <span class="post-time">
              <span class="post-meta-item-icon">
                <i class="fa fa-coffee"></i>
                <span class="post-meta-item-text">预计</span>
                <span class="post-count">45分钟</span>
              </span>
            </span>
            
		 
			
			
	  
	  
	  
	  
    </header>
  </div>

<div id="content" class="site-content">
  <div id="primary" class="content-area">
    <main id="main" class="site-main" role="main">
      <article id="post-1" class="post-1 post type-post status-publish format-standard has-post-thumbnail hentry category-uncategorized">
        <div class="toc"></div>
        <!--<div class="toc-entry-content"><!-- 套嵌目录使用（主要为了支援评论）-->
        
        <div class="entry-content">
          <h1 id="LeetCode刷题集锦"><a href="#LeetCode刷题集锦" class="headerlink" title="LeetCode刷题集锦"></a>LeetCode刷题集锦</h1><h2 id="5-最长回文子串"><a href="#5-最长回文子串" class="headerlink" title="5. 最长回文子串"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-palindromic-substring/">5. 最长回文子串</a></h2><h3 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h3><p>给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。</p>
<pre><code>示例 1：

输入: &quot;babad&quot;
输出: &quot;bab&quot;
注意: &quot;aba&quot; 也是一个有效答案。
示例 2：

输入: &quot;cbbd&quot;
输出: &quot;bb&quot;</code></pre><h3 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h3><p>①想到最优子结构</p>
<p>大字符串是回文，把首尾字符取去掉后小字符串也是回文   aba是回文，取首尾后子串b也是</p>
<p>②最小子问题</p>
<p>只有一个字母，必定是回文</p>
<p>有两个子母且两个字母相等才是回文</p>
<p>③状态转移方程     最小子问题如何推出大问题<br>$$<br>dp(i,j)=\begin{cases}<br>true &amp; i==j只有一个字母 \<br>str[j]==str[i] &amp; j-i==1两个子母 \<br>dp(i+1,j-1)且str[j]==str[i] &amp;j-i&gt;1 大于两个字母<br>\end{cases}<br>$$<br>④实现动态规划</p>
<p>dp二维数组表示【i，j】范围子串是否为回文，注意遍历的顺序，当大于两个字母时要左下的数组值才能使用状态转移，所以遍历从最后行自左向右遍历</p>
<h3 id="实现代码"><a href="#实现代码" class="headerlink" title="实现代码"></a>实现代码</h3><pre class=" language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">longestPalindrome</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    result_s<span class="token punctuation">,</span>result_e <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span>
    length <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
    dp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span> length<span class="token punctuation">)</span>


    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> length<span class="token number">-1</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span> length<span class="token punctuation">)</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> i<span class="token operator">:=</span>length<span class="token number">-1</span><span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span>i<span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>length<span class="token number">-1</span><span class="token punctuation">;</span>j<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> i<span class="token operator">==</span>j <span class="token operator">||</span> <span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">==</span><span class="token number">1</span> <span class="token operator">&amp;&amp;</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>s<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">></span><span class="token number">1</span> <span class="token operator">&amp;&amp;</span> dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span> <span class="token operator">&amp;&amp;</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>s<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i <span class="token operator">></span> result_e<span class="token operator">-</span>result_s<span class="token punctuation">)</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                    result_s<span class="token punctuation">,</span>result_e <span class="token operator">=</span> i<span class="token punctuation">,</span>j
                <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
            <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span><span class="token keyword">else</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span>
            <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> s<span class="token punctuation">[</span>result_s<span class="token punctuation">:</span>result_e<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span>

<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span></code></pre>
<h2 id="62-不同路径"><a href="#62-不同路径" class="headerlink" title="62. 不同路径"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/unique-paths/">62. 不同路径</a></h2><h3 id="题目描述-1"><a href="#题目描述-1" class="headerlink" title="题目描述"></a>题目描述</h3><p>点链接</p>
<h3 id="解题思路-1"><a href="#解题思路-1" class="headerlink" title="解题思路"></a>解题思路</h3><p>①想到最优子结构</p>
<p>到图中某一点的步数取决于其上方和左方两个位置的走法</p>
<p>②最小子问题</p>
<p>在起点，不用走只有一种走法</p>
<p>③状态转移方程     最小子问题如何推出大问题<br>$$<br>dp(i,j)=\begin{cases}<br>1 &amp; i=0||j=0 \<br>dp(i-1,j)+dp(i,j-1) &amp;j!=0||i!=0&gt;1<br>\end{cases}<br>$$<br>④实现动态规划</p>
<h3 id="实现代码-1"><a href="#实现代码-1" class="headerlink" title="实现代码"></a>实现代码</h3><p>注：实现代码多用了一行一列省去了对边界条件的判断</p>
<pre class=" language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">uniquePaths</span><span class="token punctuation">(</span>m <span class="token builtin">int</span><span class="token punctuation">,</span> n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
     dp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
     <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
         dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
     <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>dp<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span>
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token punctuation">]</span>

<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span></code></pre>
<h2 id="63-不同路径-II"><a href="#63-不同路径-II" class="headerlink" title="63. 不同路径 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/unique-paths-ii/">63. 不同路径 II</a></h2><h3 id="题目描述-2"><a href="#题目描述-2" class="headerlink" title="题目描述"></a>题目描述</h3><p>点链接</p>
<h3 id="解题思路-2"><a href="#解题思路-2" class="headerlink" title="解题思路"></a>解题思路</h3><p>①想到最优子结构</p>
<p>到图中某一点的步数取决于其上方和左方两个位置的走法</p>
<p>②最小子问题</p>
<p>在起点，不用走只有一种走法</p>
<p>在障碍物点上，可能的结果为0中</p>
<p>③状态转移方程     最小子问题如何推出大问题<br>$$<br>dp(i,j)=\begin{cases}<br>1 &amp; (i=0||j=0)且obstacleGrid[i][j]==0 \<br>0 &amp; obstacleGrid[i][j]==1\<br>对应上一步位置不是障碍物的点dp(i-1,j)+dp(i,j-1) &amp;obstacleGrid[i][j]==0且(i!=0)且j!=0<br>\end{cases}<br>$$<br>④实现动态规划</p>
<h3 id="实现代码-2"><a href="#实现代码-2" class="headerlink" title="实现代码"></a>实现代码</h3><pre class=" language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">uniquePathsWithObstacles</span><span class="token punctuation">(</span>obstacleGrid <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    m<span class="token punctuation">,</span>n <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
     dp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> m<span class="token punctuation">)</span>
     <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
         dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span>
     <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
     <span class="token comment" spellcheck="true">//初始化</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

     <span class="token comment" spellcheck="true">//迭代</span>
     <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
         <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
             <span class="token keyword">if</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//该点不可达</span>
                 dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span>
             <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span><span class="token keyword">else</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//该点可达</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isValiated</span><span class="token punctuation">(</span>i<span class="token number">-1</span><span class="token punctuation">,</span>j<span class="token punctuation">,</span>m<span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span>obstacleGrid<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+=</span> dp<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
                <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isValiated</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span>j<span class="token number">-1</span><span class="token punctuation">,</span>m<span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span>obstacleGrid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+=</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span>
                <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
             <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
         <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
     <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>m<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token number">-1</span><span class="token punctuation">]</span>

<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

<span class="token keyword">func</span> <span class="token function">isValiated</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> j <span class="token punctuation">,</span> m<span class="token punctuation">,</span> n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span><span class="token number">0</span> <span class="token operator">||</span> j<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>i<span class="token operator">>=</span>m <span class="token operator">||</span>j<span class="token operator">>=</span>n<span class="token punctuation">)</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> <span class="token boolean">false</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
</code></pre>
<h2 id="64-最小路径和"><a href="#64-最小路径和" class="headerlink" title="64. 最小路径和"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/minimum-path-sum/">64. 最小路径和</a></h2><h3 id="题目描述-3"><a href="#题目描述-3" class="headerlink" title="题目描述"></a>题目描述</h3><h3 id="解题思路-3"><a href="#解题思路-3" class="headerlink" title="解题思路"></a>解题思路</h3><p>先想到最优子结构，到某一点路径和最小其实就是到上、左两侧点最小路径和   中的最小值+本点的值</p>
<p>然后想最小子问题</p>
<p>然后想状态转移方程，如何大问题如何化为更小的问题</p>
<p>最后代码实现 可以自底向上迭代   也可自顶向下递归  +备忘录</p>
<h3 id="实现代码-3"><a href="#实现代码-3" class="headerlink" title="实现代码"></a>实现代码</h3><pre class=" language-c++"><code class="language-c++">class Solution &#123;
    public int minPathSum(int[][] grid) &#123;
        if (grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1) &#123;
            return 0;
        &#125;

        int row = grid.length;
        int col = grid[row - 1].length;

        int dp[][] = new int[row][col];

        dp[0][0] = grid[0][0];

        for (int i = 1;i < row;i++) &#123;
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        &#125;

        for (int i = 1;i < col;i++) &#123;
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        &#125;

        for (int i = 1;i < row;i++) &#123;
            for (int j = 1;j < col;j++) &#123;
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            &#125;
        &#125;

        return dp[row - 1][col - 1];
    &#125;
&#125;</code></pre>
<h3 id=""><a href="#" class="headerlink" title=""></a></h3><h2 id="91-解码方法"><a href="#91-解码方法" class="headerlink" title="91. 解码方法"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/decode-ways/">91. 解码方法</a></h2><h3 id="题目描述-4"><a href="#题目描述-4" class="headerlink" title="题目描述"></a>题目描述</h3><h3 id="解题思路-4"><a href="#解题思路-4" class="headerlink" title="解题思路"></a>解题思路</h3><p>求最优子结构：长的字符的编码可能等于  删去一个字符、删去两个字符的可能之和</p>
<p>最小子问题：只有一个字符时  为0  没有可能   不为0    有1中可能</p>
<p>状态转移方程：<br>$$<br>dp(i)=\begin{cases}<br>1 &amp; i==0||i==1\<br>dp[i-1]+dp[i-2] &amp;i&gt;1<br>\end{cases}<br>\备注：dp[i-1]条件：str[i]!=’0’;dp[i-2]条件：str[i]==’1’||(str[i]==2&amp;&amp;‘0’&lt;=str[i-1]&lt;=’6’)<br>$$</p>
<h3 id="实现代码-4"><a href="#实现代码-4" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func numDecodings(s string) int &#123;
    if(s[0] == &#39;0&#39;) &#123;
        return 0
    &#125;
    dp := make([]int, len(s)+1)
    dp[0],dp[1] = 1,1 //0是为了当只有两个字符时如果删去两个字符dp[0]表示算为有一种可能

    for i:=2; i&lt;len(s)+1; i++ &#123;

        if(s[i-1]!=&#39;0&#39;)&#123;
            dp[i] = dp[i] + dp[i-1]
        &#125;
        if(s[i-2]==&#39;1&#39;||(s[i-2]==&#39;2&#39; &amp;&amp; s[i-1]&lt;=&#39;6&#39; &amp;&amp; s[i-1]&gt;=&#39;0&#39;)) &#123;
                dp[i] = dp[i]+dp[i-2]
        &#125;

    &#125;
    return dp[len(s)]
&#125;</code></pre><h3 id="难点备注"><a href="#难点备注" class="headerlink" title="难点备注"></a>难点备注</h3><p>当只有两个数字时对于dp[i-2]会出现越界的情况，所以dp数组比字符串长度多一位，用最后一位为1表示当两个数字可以解码成字母时会+1</p>
<h2 id="120-三角形最小路径和"><a href="#120-三角形最小路径和" class="headerlink" title="120. 三角形最小路径和"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/triangle/">120. 三角形最小路径和</a></h2><h3 id="解题思路："><a href="#解题思路：" class="headerlink" title="解题思路："></a>解题思路：</h3><p>最优子结构   最小子问题   状态转移方程    迭代+dp数组代码实现</p>
<h3 id="实现代码-5"><a href="#实现代码-5" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func minimumTotal(triangle [][]int) int &#123;
    if(triangle==nil) &#123;
        return 0
    &#125;
    width,length := len(triangle),len(triangle) 
    dp  := make([][]int, width)
    for i:=0;i&lt;width;i++ &#123;
        dp[i] = make([]int, length)
    &#125;

    dp[0][0] = triangle[0][0]
    for i:=1; i&lt;width;i++&#123;
        for j:=0; j&lt;=i;j++&#123;
            dp[i][j] = 100000
            if(j-1&gt;=0) &#123;
                dp[i][j] = dp[i-1][j-1] +triangle[i][j]
            &#125;
             if(j &lt;= i-1 &amp;&amp;dp[i][j] &gt; dp[i-1][j] + triangle[i][j]) &#123;
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            &#125;
        &#125;
    &#125;
    min := dp[width-1][0]
    for i:=1;i&lt;length;i++ &#123;
        if(min &gt; dp[width-1][i]) &#123;
            min = dp[width-1][i]
        &#125;
    &#125;
    return min
&#125;</code></pre><h3 id="空间压缩优化"><a href="#空间压缩优化" class="headerlink" title="空间压缩优化"></a>空间压缩优化</h3><p>dp[i][j]=min(dp[i-1][j-1], dp[i-1][j])本层和上面一整层有关系，而一层最多有n各个元素，所以空间可压缩到O(n)</p>
<p>所以先想到两个一维数组的方法</p>
<pre><code>func minimumTotal(triangle [][]int) int &#123;
    if(triangle==nil) &#123;
        return 0
    &#125;
    length := len(triangle)
    if(length == 1) &#123;
        return triangle[0][0]
    &#125;
    dp  := make([][]int, 2) // 压缩空间
    dp[0] = make([]int, length)
    dp[1] = make([]int, length)

    dp[0][0] = triangle[0][0]
    for i:=1; i&lt;length;i++&#123;
        for j:=0; j&lt;=i;j++&#123;
            min := 100000
            if(j-1&gt;=0) &#123;
                min =  dp[0][j-1]+triangle[i][j]
            &#125;
             if(j &lt;= i-1 &amp;&amp;min &gt; dp[0][j] + triangle[i][j]) &#123;
                min = dp[0][j] + triangle[i][j]
            &#125;
            dp[1][j] = min
        &#125;
        for k:=0;k&lt;length;k++&#123;
            dp[0][k] = dp[1][k]
        &#125;

    &#125;
    min := dp[1][0]
    for i:=1;i&lt;length;i++ &#123;
        if(min &gt; dp[1][i]) &#123;
            min =dp[1][i]
        &#125;
    &#125;
    return min
&#125;</code></pre><h3 id="继续优化"><a href="#继续优化" class="headerlink" title="继续优化"></a>继续优化</h3><p>使用奇数偶数可以省去循环中dp[1][]导入到dp[0][]</p>
<p>进一步优化的话是第二层循环j的那一层使用倒着遍历方法，只用一个数组就行可以避免dp[j]用到dp[j] 、dp[j-1]正向遍历</p>
<p>dp[1]改了dp[1],但是dp[2]还要用dp[1]  如果倒着遍历则可以不影响了。可见逆向思维</p>
<h2 id="309-最佳买卖股票时机含冷冻期"><a href="#309-最佳买卖股票时机含冷冻期" class="headerlink" title="309. 最佳买卖股票时机含冷冻期"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/">309. 最佳买卖股票时机含冷冻期</a></h2><p>解题思路：</p>
<p>①找最优子结构:</p>
<p>这个题不太好找，  自变量、因变量的确定</p>
<p>首先是变量种类多:天数、最大利益、好几种不同的选择</p>
<p>这个时候我们不能一眼看出最优子结构，不想走到某地的走法数，有明显的递推关系</p>
<p>第n天的最大利益取决于前面一系列的选择，且第n天取最大利益和第1天取最大利益可能不一样</p>
<p><strong>一方面当我们定了一个自变量和因变量(状态)时，要进行验证是否合适(如何判断合不合适？)</strong></p>
<p><strong>另一方面当一眼看不出来后就不能靠猜的了，此时第一步先把所有选择对应的转换情况写出如下:</strong></p>
<p>第n天可能的情况，则第n+1天的可能情况</p>
<p><img src="" alt="image -w150 -"></p>
<p>通过图我们知道什么因变量(状态)彼此相关可以递推呢?一天的三种状态,到下一天的转换</p>
<p>这个和我们的最大利益值有关系吗？知道第1天三种状态的利益，那第二天三种状态的利益自然也可以知道,对于第二天的卖的状态，是由第一天卖第一天持有股票什么也不做得到的，那 我们只保留最大的利益</p>
<p>这样每一天的三种状态的最大利益就可以递推了</p>
<p>这样依次推到第n天的利益</p>
<p>所以状态自变量定义为三种状态的最大利益    因变量为天数</p>
<p>总结：最优子结构为如果今天卖股票 最大利益  等于   昨天买入股票最大利益和昨天什么不做持有股票的最大利益  两者最大值</p>
<p>②最小子问题，</p>
<p>第一天 没有股票不在冷冻期：0       有股票不在冷冻期:0(这个不存在,递推第二天是要忽略的)     没有股票但在冷冻期:0 (这个是不存在的在第一天,递推第二天时要忽略掉)            </p>
<p>为了递推时要对第一天特殊处理，所以把第二天直接写出来</p>
<p>第二天 没有股票不在冷冻期：0       有股票不在冷冻期：max(-prices[0],-price[1])     没有股票但在冷冻期:price[1]-price[0]  </p>
<p>③递推公式</p>
<p>$$<br>没有股票不在冷冻期:dp[0][n]=max(dp[0][n-1],dp[2][n-1])<br>\<br>有股票不在冷冻期:dp[1][n]=max(dp[0][n-1]-prices[i]，dp[1][n-1])<br>\<br>没有股票但在冷冻期:dp[2][n]=max(dp[1][n]+prices[i])</p>
<p>\备注:当n大于1时才执行递推，否则就按最小子问题处理<br>$$</p>
<p>在画图基础上定下自变量和因变量和我们猜的,如天数、最大利益（无法递推）；  天数+每天做的选择、最大利益(没有递推关系)，这个最大利益做为因变量怎么都无法递推，因为最大利益和每一天的选择都有关系</p>
<h3 id="代码编写"><a href="#代码编写" class="headerlink" title="代码编写"></a>代码编写</h3><pre><code>func maxProfit(prices []int) int &#123;
    if prices==nil||len(prices)==0||len(prices)==1&#123;
        return 0
    &#125;

    dp := make([][]int, 3)
    for i:=0;i&lt;3;i++ &#123;
        dp[i] = make([]int, len(prices))
    &#125;

    dp[0][1] = 0
    dp[1][1] = max(-prices[1],-prices[0])
    dp[2][1] = prices[1]-prices[0]
    for i:=2;i&lt;len(prices);i++ &#123;
        dp[0][i] = max(dp[0][i-1],dp[2][i-1])
        dp[1][i]=max(dp[0][i-1] - prices[i],dp[1][i-1])
        dp[2][i]=dp[1][i-1]+prices[i]
    &#125;
    return max(dp[0][len(prices)-1], dp[2][len(prices)-1])
&#125;
func max (a,b int) int &#123;
    if a&gt;b &#123;
        return a
    &#125;else&#123;
        return b
    &#125;
&#125;</code></pre><h2 id="122-买卖股票的最佳时机-II"><a href="#122-买卖股票的最佳时机-II" class="headerlink" title="122. 买卖股票的最佳时机 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/">122. 买卖股票的最佳时机 II</a></h2><h3 id="解题思路-5"><a href="#解题思路-5" class="headerlink" title="解题思路"></a>解题思路</h3><p>每天有两种状态  可买、可卖</p>
<h3 id="实现代码-6"><a href="#实现代码-6" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func maxProfit(prices []int) int &#123;
    if(prices == nil || len(prices)==0) &#123;
        return 0
    &#125;
    dp := make([][]int,2)
    dp[0] = make([]int, len(prices))
    dp[1] = make([]int, len(prices))
    dp[0][0],dp[1][0] = 0, 0-prices[0]
    for i:=1;i&lt;len(prices);i++ &#123;
        dp[0][i] = max(dp[0][i-1], dp[1][i-1]+prices[i])
        dp[1][i] = max(dp[1][i-1], dp[0][i-1]-prices[i])
    &#125;
    return dp[0][len(prices)-1]

&#125;

func max(a,b int) int&#123;
    if a&gt;b&#123;
        return a
    &#125;
    return b
&#125;</code></pre><h2 id="121-买卖股票的最佳时机"><a href="#121-买卖股票的最佳时机" class="headerlink" title="121. 买卖股票的最佳时机"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/">121. 买卖股票的最佳时机</a></h2><h3 id="解题思路-6"><a href="#解题思路-6" class="headerlink" title="解题思路"></a>解题思路</h3><p>每日有三个状态  没买过可以买股票、买过但还没有卖、买过而且也卖了 彼此之间转化递推，</p>
<p>如果当天某一状态要去最大利益，取决于昨天可以变为该状态的最大利益加上相应操作带来的影响</p>
<h3 id="实现代码-7"><a href="#实现代码-7" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>    func maxProfit(prices []int) int &#123;
        if(prices==nil || len(prices)==0) &#123;
            return 0
        &#125;
        length := len(prices) 
        dp := make([][]int, 3)
        for i:=0;i&lt;3;i++&#123;
            dp[i]=make([]int, length)
        &#125;
        dp[0][0],dp[1][0],dp[2][0] = 0,0-prices[0],0
        for i:=1;i&lt;length;i++ &#123;
            dp[0][i] = 0
            dp[1][i] = max(dp[1][i-1], dp[0][i-1]-prices[i])
            dp[2][i] = max(dp[2][i-1], dp[1][i-1]+prices[i])
        &#125;
        return dp[2][length-1]
    &#125;

    func max(a, b int)  int&#123;
        if(a&gt;b) &#123;
            return a
        &#125;
        return b
    &#125;</code></pre><h2 id="322-零钱兑换"><a href="#322-零钱兑换" class="headerlink" title="322. 零钱兑换"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-change/">322. 零钱兑换</a></h2><h3 id="解题思路-7"><a href="#解题思路-7" class="headerlink" title="解题思路"></a>解题思路</h3><p>凑大钱由凑小钱转移而来 ，有1、2、5三种硬币，    凑11元钱 最少      肯定是   凑11-1    11-2     11-5三种情况中最少硬币数+1</p>
<p>如果三种都没办法凑，那11块钱也没办法凑</p>
<p>最小子问题 dp[0] = 0</p>
<p>$$<br>dp[i]=min\begin{cases}<br>dp[i-coin[1]] &amp; i-coin[1]&gt;=0\<br>……\<br>dp[i-coin[2]] &amp; i-coin[2]&gt;=0<br>\end{cases}+1\或者当没有i-coin&gt;=0时dp[i]为-1,凑不成<br>$$</p>
<h3 id="实现代码-8"><a href="#实现代码-8" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func coinChange(coins []int, amount int) int &#123;
    dp := make([]int, amount+1)
    dp[0] = 0
    for i:=1;i&lt;=amount;i++ &#123;
        min := 10000 //表示不可达
        for _, j := range coins &#123;
            if(i-j &gt;= 0 &amp;&amp; dp[i-j]!=-1 &amp;&amp;dp[i-j]&lt;min) &#123;
                min = dp[i-j]
            &#125;
        &#125;
        //如果仍是最大值  表示没有可达
        if min == 10000 &#123;
            dp[i] = -1
        &#125;else &#123;
            dp[i] = min+1
        &#125;
    &#125;
    return dp[amount]
&#125;</code></pre><h2 id="198-打家劫舍"><a href="#198-打家劫舍" class="headerlink" title="198. 打家劫舍"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber/">198. 打家劫舍</a></h2><h3 id="解题思路-8"><a href="#解题思路-8" class="headerlink" title="解题思路"></a>解题思路</h3><p>不能连续偷东西，  每一间房子有两种状态   (可以偷不会触发警报  、  不可以偷会触发警报)</p>
<p>每经过一间房子都会有什么也不做、偷东西两种动作</p>
<p><strong>最小问题</strong>   只有一间房子</p>
<p>dp[0][0] = 0  //第1间可以偷不会触发警报</p>
<p><strong>状态转移方程</strong></p>
<p>dp[1][0] = nums[0] //第1间 不可以偷会触发警报<br>$$<br>dp[0][i] = \begin{cases} max(dp[1][i-1],dp[0][i-1]) &amp; i-1房 什么也不做，i-1偷过东西\end{cases}<br>\</p>
<p>dp[1][i] = \begin{cases} dp[0][i-1]+nums[i] &amp;i-1房 可以偷 \end{cases}<br>$$</p>
<h3 id="实现代码-9"><a href="#实现代码-9" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>  func rob(nums []int) int &#123;
        if(nums==nil ||len(nums)==0)&#123;
            return 0
        &#125;
        length := len(nums)
        dp:=make([][]int, 2)
        dp[0] =make([]int, length)
        dp[1] =make([]int,length)
        dp[0][0],dp[1][0] = 0,nums[0]
        for i:=1;i&lt;length;i++ &#123;
            dp[0][i]=max(dp[0][i-1],dp[1][i-1])
            dp[1][i]=dp[0][i-1]+nums[i]
        &#125;
        return max(dp[0][length-1],dp[1][length-1])
    &#125;
    func max(a, b int) int &#123;
        if a&gt;b&#123;
            return a
        &#125;
        return b
    &#125;</code></pre><h2 id="343-整数拆分"><a href="#343-整数拆分" class="headerlink" title="343. 整数拆分"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/integer-break/">343. 整数拆分</a></h2><h3 id="解题思路-9"><a href="#解题思路-9" class="headerlink" title="解题思路"></a>解题思路</h3><p>这道题怎么说，不是多阶段决策达到最优解这一类型，而是大问题化小问题的分治法问题</p>
<p>大数N的拆分的最大乘机  如果只拆成两个数 有 1,n-1   2,n-2    3,n-3  …… [n/2-1,n/2]     奇数偶数情况不一致</p>
<p>拆成两个数后又可再拆，那就是子问题，如2，n-2       n-2的拆分方式一定是最大乘积</p>
<p>所以大数N的拆分用到了子问题拆分情况 </p>
<p>但是注意一点 大数N   拆成2,N-2   后  N-2可以继续拆也可以不拆  这是两种情况</p>
<p>对于   N-2,2 拆不拆2</p>
<p>对于2,N-2拆不拆N-2</p>
<p>总结 </p>
<p>最小子问题是n=0    n=1是最大乘积为0（不可以拆分成两个正整数）    n=2时 最大乘积为1</p>
<p>之后对于n&gt;2，<strong>大数N拆成两个数的所有情况   如2,N -2  可以①N-2不拆，2<em>N-2     ②N-2拆   子问题拆(N-2)\</em>2</strong></p>
<p>所以状态转移方程为</p>
<p>$$<br>状态转移方程<br>\<br>dp[n] = \begin{cases}<br>max \big[ i<em>(n-i),i</em>dp[n-i]) \big] &amp;&amp; n &gt;2<br>\end{cases}<br>\备注i从1遍历到n-1<br>$$</p>
<h3 id="实现代码-10"><a href="#实现代码-10" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func integerBreak(n int) int &#123;
    dp := make([]int, n+1)
    dp[0], dp[1], dp[2] = 0, 0, 1
    for i:=3;i&lt;=n;i++ &#123;
        tmp_max := 0
        for j:=1;j&lt;i;j++ &#123;
            no_chai,chai :=j*(i-j),j*dp[i-j]
            tmp_max = max(no_chai, chai, tmp_max)
        &#125;
        dp[i] = tmp_max
    &#125;
    return dp[n]
&#125;

//三个数求最大
func max(x,y,z int) int &#123;
    max := x
    if y&gt;max &#123;
        max =y
    &#125;
    if z&gt;max &#123;
        max =z
    &#125;
    return max 
&#125;</code></pre><p>分析问题：对于不是分阶段决策的问题，而是分治法大问题套用小问题的解这种情况，要先写出递归解法，把规律找到</p>
<p>如本题   拆分大问题      只拆成两个数i,n-i 、 继续拆n-i 两种情况最大值    继续拆n-i可以递归调用</p>
<p>我们将原问题抽象为 f(n)<br>那么 f(n) 等价于 max(1 * f(n - 1), 2 * f(n - 2), …, (n - 1) * f(1))  +  只拆分成两个数1*n-1    2*n-2 ……的情况。</p>
<h2 id="152-乘积最大子数组"><a href="#152-乘积最大子数组" class="headerlink" title="152. 乘积最大子数组"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-product-subarray/">152. 乘积最大子数组</a></h2><h3 id="解题思路-10"><a href="#解题思路-10" class="headerlink" title="解题思路"></a>解题思路</h3><p>暴力解决就是遍历所有i,j的组合可能</p>
<p>这道题还是要向分治方法求解问题，找出大小问题之间的关联</p>
<p>以i为结尾连续子数组的最大乘积，和以i-1结尾的最大乘积之间的关系</p>
<p><strong>可以用以i-1结尾的最大乘积*nums[i],也可以不用前i-1个元素只用nums[i]</strong></p>
<p>备注：这是如何想出来的？连乘关系，nums[i]可能为正负，前面的连乘可能为正负，我们的nums[i]可以并入前面或者不并入前面，</p>
<p>这里很容易忽略第三种情况即 以i-1为结尾的最小乘积*nums[i]负负得正变成了最大，综上  以i为结尾的最大乘积的设为dp[0][i],以i为结尾的最小乘积设为dp[1][i],有三种可能得到       </p>
<p>①dp[0][i-1]*nums[i]</p>
<p>②dp[1][i-1]*nums[i]</p>
<p>③nums[i]</p>
<p>对于dp[1][i-1]也是从上面的三种可能得到</p>
<p>最小子问题： dp[0]][0]=nums[i]    dp[1][0]=nums[i]</p>
<p>状态转移方程<br>$$<br>dp[0][i]=MAX\big[ (dp[0][i-1]<em>nums[i]), (dp[1][i-1]</em>nums[i], nums[i])         \big]\<br>dp[0][i]=MIN\big[ (dp[0][i-1]<em>nums[i]), (dp[1][i-1]</em>nums[i]), nums[i]         \big]<br>\从两种情况中取最大值、最小值<br>$$</p>
<h3 id="实现代码-11"><a href="#实现代码-11" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func maxProduct(nums []int) int &#123;
    dp := make([][]int, 2)
    dp[0] = make([]int, len(nums))
    dp[1] = make([]int, len(nums))
    dp[0][0], dp[1][0] = nums[0], nums[0]
    for i:=1; i &lt; len(nums);i++ &#123;
        dp[0][i] = Max(dp[0][i-1]*nums[i], dp[1][i-1]*nums[i], nums[i])
        dp[1][i] = Min(dp[0][i-1]*nums[i], dp[1][i-1]*nums[i], nums[i])
    &#125;
    max := -100000
    for _,i:=range dp[0] &#123;
        if max &lt; i &#123;
            max = i
        &#125;
    &#125;
    return max
&#125;

func Max(x, y, z int) int &#123;
    max := x
    if y&gt;max &#123;
        max =y
    &#125;

    if z&gt;max &#123;
        max =z
    &#125;
    return max
&#125;

func Min(x, y, z int) int &#123;
    min := x
    if y&lt;min &#123;
        min =y
    &#125;

    if z&lt;min &#123;
        min =z
    &#125;
    return min
&#125;</code></pre><h2 id="300-最长上升子序列"><a href="#300-最长上升子序列" class="headerlink" title="300. 最长上升子序列"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-increasing-subsequence/">300. 最长上升子序列</a></h2><h3 id="解题思路-11"><a href="#解题思路-11" class="headerlink" title="解题思路"></a>解题思路</h3><p>自变量：考虑到第i个数字</p>
<p>状态考虑:</p>
<p>①前i个数最长上升子序列的长度</p>
<p>状态之间没有关联，知道前i的最长，但是前i+1的也没有足够的 信息推出来——因为我们不知道前i最长是那几个数，第i+1的数又是否可以接上去</p>
<p>②以第i个数结尾的最长上升子序列长度</p>
<p><strong>知道前i个数结尾的最长长度，可以判断第i+1个数是否可以接到后面,</strong></p>
<p><strong>第i+1个数比后面i个数大则可以接上，总可以接上的所有可能中选出最长的情况</strong></p>
<p>最小子问题:dp[0]=1 只有一个数字</p>
<p>转载leetcode的图<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/tu-jie-zui-chang-shang-sheng-zi-xu-lie-by-cheng-xu/">https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/tu-jie-zui-chang-shang-sheng-zi-xu-lie-by-cheng-xu/</a></p>
<p><img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20201208202104.png" alt="2595a56ba8d47cd9d4690bd2125cea57840a7515d0d900a4ee2c939f1191cc11-图片"></p>
<p>$$<br>状态转移方程\<br>dp[i]=\begin{cases}<br>MAX \bigg(dp[j]+1\bigg) &amp;j从0到i-1,且nums[i]&gt;nums[j]<br>\end{cases}<br>\<br>如果nums[i]比前面的nums[j]都大则dp[i]=1<br>$$</p>
<h3 id="实现代码-12"><a href="#实现代码-12" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func lengthOfLIS(nums []int) int &#123;
    if len(nums)==0 &#123;
        return 0
    &#125;
    result := 1
    dp := make([]int, len(nums))
    dp[0] = 1
    for i:=1;i&lt;len(nums);i++ &#123;
        max := 1
        for j:=0; j&lt;i; j++&#123;
            if dp[j]+1 &gt; max &amp;&amp; nums[i] &gt;  nums[j] &#123;
                max = dp[j]+1
            &#125;
        &#125;
        dp[i] = max
        if result &lt; dp[i] &#123;
            result = dp[i]
        &#125;
    &#125;
    return result

&#125;</code></pre><p>复杂度为O(n<sup>2</sup>),空间复杂度O(n)</p>
<h3 id="进一步优化"><a href="#进一步优化" class="headerlink" title="进一步优化"></a>进一步优化</h3><p>将复杂度变为O(nlogn)</p>
<p>思路：贪心算法+二分查找</p>
<p>贪心算法要每次做的选择得到最优解，连续做的最优选择就时最后的解</p>
<p>我们每次做的最有选择就是 尽可能的缩短我们上升子序列的最大值</p>
<p>当nums[i+1] &gt; nums[i],可以放入一个数据</p>
<p>当nums[i+1] &lt;=nums[i] 将其替换第一个小于nums[i]的数，这样我们可以尽可能的多放进</p>
<h2 id="354-俄罗斯套娃信封问题"><a href="#354-俄罗斯套娃信封问题" class="headerlink" title="354. 俄罗斯套娃信封问题"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/russian-doll-envelopes/">354. 俄罗斯套娃信封问题</a></h2><p> 将其按w递增排序，同样的h按递减排序就变成了最长上升子序列问题</p>
<h3 id="实现代码-13"><a href="#实现代码-13" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>import (
    &quot;fmt&quot;
    &quot;sort&quot;
)
func maxEnvelopes(envelopes [][]int) int &#123;
    sort.Slice(envelopes, func (i, j int)bool &#123;
        if envelopes[i][0]==envelopes[j][0]&#123;
            return envelopes[i][1] &gt; envelopes[j][1]
        &#125;
        return envelopes[i][0] &lt; envelopes[j][0]
    &#125;)
    return maxLength(envelopes[:][1])

&#125;

//最长上升子序列
func maxLength(nums []int) int&#123; 
    length := len(nums)
    if length == 0 &#123;
        return 0
    &#125;
    dp := make([]int ,length)
    dp[0] = 1
    for i:=1;i&lt;length;i++ &#123;
        dp[i] = 1
        for j:=0;j&lt;i;j++ &#123;
            if nums[i]&gt;nums[j] &amp;&amp; dp[i] &lt; dp[j]+1 &#123;
                dp[i] = dp[j]+1
            &#125;
        &#125;

    &#125;
    max := dp[0]
    for k:=0;k&lt;length;k++ &#123;
        if max &lt; dp[k] &#123;
            max = dp[k]
        &#125;
    &#125;
    return max
&#125;</code></pre><h3 id="引申"><a href="#引申" class="headerlink" title="引申"></a>引申</h3><p>对于三维的嵌套问题，则要去引入<strong>树状数组</strong>这一结构来解决问题，问题更复杂</p>
<h2 id="213-打家劫舍-II"><a href="#213-打家劫舍-II" class="headerlink" title="213. 打家劫舍 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber-ii/">213. 打家劫舍 II</a></h2><h3 id="解题思路-12"><a href="#解题思路-12" class="headerlink" title="解题思路"></a>解题思路</h3><p>和打家劫舍很像，只是第1和第n间房有冲突关系</p>
<p>我们可以假设两种情况</p>
<p>第一间偷，第2不可偷   第3~第n-1间房用动态规划求得最大价值</p>
<p>第一间不偷，第2~第n间房用动态规划求得最大价值</p>
<p>动态规划问题就是不能连续偷的情况下可获得的最大价值</p>
<p><img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20201209215715.png" alt="image-20201209215711213"></p>
<p>每一间房有两个状态dp[0]没动，dp[1]偷了<br>$$<br>没动dp[0][i]=<br>max\bigg(dp[0][i-1]+nums[i],dp[1][i-1]\bigg)</p>
<p>\<br>偷了dp[i][i-1]=dp[0][i-1]<br>$$<br>对于第一天偷第二天不偷，从第三天开始算    </p>
<p>第三天 没动状态  dp[1][2]  为nums[0]</p>
<p>第三天 偷了状态 不存在      dp[1][2]     特别小到第四天直接舍去 (因为第二天没有偷)</p>
<p>对于第一天不偷，从第二天开始算</p>
<p>第二天没动 dp[0][1]=0</p>
<p>第二天偷了状态 dp[1][1]=nums[1]</p>
<h3 id="实现代码-14"><a href="#实现代码-14" class="headerlink" title="实现代码"></a>实现代码</h3><p>代码不是很好，优化方案:对于动态规划重复逻辑进行复用</p>
<pre><code>func rob(nums []int) int &#123;
    length := len(nums)
    if length==0 &#123;
        return 0
    &#125;
    if length==1 &#123;
        return nums[0]
    &#125;

    dp := make([][]int, 2)
    dp[0], dp[1] = make([]int, length), make([]int, length)
    dp[0][0], dp[1][0],dp[0][1], dp[1][1] = nums[0], 0, nums[0], 0 //第一天偷了,第二天没偷
    for i:=2;i&lt;length-1;i++ &#123;
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]
    &#125;
    maxVal := max(dp[0][length-2], dp[1][length-2])
    // 重置为0
    for i:=0;i&lt;length;i++ &#123;
        dp[0][i], dp[1][i] = 0, 0
    &#125;
    dp[0][0], dp[1][0] = 0, 0 // 第一天没投
    for i:=1;i&lt;length;i++ &#123;
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]

    &#125;
    maxVal2 := max(dp[0][length-1], dp[1][length-1])

    return max(maxVal, maxVal2)

&#125;

func max(a, b int) int &#123;
    if a&gt;b &#123;
        return a
    &#125;
    return b
&#125;</code></pre><p>优化代码如下</p>
<pre><code>func rob(nums []int) int &#123;
    length := len(nums)
    if length==0 &#123;
        return 0
    &#125;
    if length==1 &#123;
        return nums[0]
    &#125;
    if length&lt;=3 &#123; // 对于长度为2的nums[2:length-1]会 出现越界异常   长度为3则是nums[2:length-1]会把第三房偷的情况也返回
        return max(nums[0],  MyRob(nums[1:length]))
    &#125;
    return max(MyRob(nums[2:length-1])+nums[0], MyRob(nums[1:length]))

&#125;

func MyRob(nums[] int) int&#123;
    length := len(nums)
    if length==0 &#123;
        return 0
    &#125;
    if length==1 &#123;
        return nums[0]
    &#125;
    dp := make([][]int, 2)
    dp[0],dp[1] = make([]int ,length), make([]int, length)

    dp[0][0], dp[1][0] = 0, nums[0]
    for i:=1;i&lt;length;i++ &#123;
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]

    &#125;
    return  max(dp[0][length-1], dp[1][length-1])

&#125;

func max(a, b int) int &#123;
    if a&gt;b &#123;
        return a
    &#125;
    return b
&#125;</code></pre><p>也可以是思路</p>
<p>在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]），最大金额是 p1</p>
<p>在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]），最大金额是 p2<br>综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)</p>
<p>作者：jyd<br>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-iidong-tai-gui-hua-jie-gou-hua-/">https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-iidong-tai-gui-hua-jie-gou-hua-/</a><br>来源：力扣（LeetCode）<br>著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</p>
<h2 id="337-打家劫舍-III"><a href="#337-打家劫舍-III" class="headerlink" title="337. 打家劫舍 III"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/house-robber-iii/">337. 打家劫舍 III</a></h2><p>解题思路：</p>
<p>树状dp问题，第一次遇见啊。</p>
<p>每一个节点定义两种状态，已偷和没动</p>
<p>状态转移如下：</p>
<p><img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20201210201300.png" alt="image-20201210201251324"></p>
<p>当前节点没动和已偷两种状态下各自可获得的最大价值</p>
<p>自变量是每一个节点，因变量是遍历顺序可以获取最大的价值</p>
<p><strong>难点是原来是数组状态转移方程就是数组dp[i],但是现在是二叉树。</strong></p>
<p>先看状态转移方程<br>$$<br>没动dp[i][0] = 所有子节点\sum max(dp[i-1][0],dp[i-1][1]) 当父节点没动子节点可偷可不偷<br>\<br>已偷dp[i][1]=所有子节点\sum dp[i-1][0] +nums[i]当父节点已偷子节点都不能偷<br>$$<br>父节点可以获取的两种状态价值取决于子节点，要先知两个子节点再求父节点—–后续遍历</p>
<pre><code>//伪代码
递归函数func(入参节点node) (返回  do已偷状态价值， undo没动状态价值) &#123;
    if node ==null &#123; 
        //节点为空，两个返回0
    &#125;

    leftDo, leftUndo =  func(左节点)的已偷 没动可获价值
    rightDo, rightUndo =  func(右节点)的已偷 没动可获价值

    //当前节点已偷=子节点没有偷的情况+当前节点的价值
    curDo = leftUndo + rightDo + nums[cur] 
    //当前节点没动=子节点偷或不偷两种状态可获价值最大值
    curUndo = max(leftDo, leftUndo)+max(rightDo, rightUndo)  
&#125;</code></pre><p>这样我们可以获取到根节点的两种状态的最大价值，取个最大值即可</p>
<h3 id="实现代码-15"><a href="#实现代码-15" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>/**
 * Definition for a binary tree node.
 * type TreeNode struct &#123;
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * &#125;
 */
func rob(root *TreeNode) int &#123;
    return max(doRob(root))
&#125;

func doRob(node *TreeNode) (int, int) &#123;
    if node == nil &#123;
        return 0, 0
    &#125;
    lundo, ldo := doRob(node.Left)
    rundo, rdo := doRob(node.Right)    
    return  max(lundo, ldo) + max(rundo, rdo), lundo+rundo+node.Val
&#125;

func max(a,b int) int &#123;
    if a&gt;b &#123;
        return a
    &#125;
    return b
&#125;</code></pre><h2 id="375-猜数字大小-II"><a href="#375-猜数字大小-II" class="headerlink" title="375. 猜数字大小 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/">375. 猜数字大小 II</a></h2><h3 id="解题思路-13"><a href="#解题思路-13" class="headerlink" title="解题思路"></a>解题思路</h3><p>MiniMAX—最小化对方最大收益的问题，比如下棋如何下会使对方的收益最小，博弈树</p>
<p>我们的任务是猜数，那无疑会有好多种情况，  我们猜的顺序和对方选择的数都是不同的组合<br>问题求的是我们最多花多少钱稳赢</p>
<p>这里给一下其他人的解释：原链接<a target="_blank" rel="noopener" href="https://www.cnblogs.com/fayin/p/10407176.html">https://www.cnblogs.com/fayin/p/10407176.html</a></p>
<p>题目下方给出了几个提示：</p>
<ul>
<li>游戏的最佳策略是减少最大损失，这引出了 Minimax 算法，见<a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Minimax">这里</a>，和<a target="_blank" rel="noopener" href="https://univasity.iteye.com/blog/1170216">这里</a></li>
<li>使用较小的数开始（例如3），看看在最差的情况下你要支付多少钱？</li>
<li>即使 n 比较小，完全使用递归的效率也很低，试试动态规划吧。</li>
</ul>
<p>我们就按照上面的提示玩一把：猜数字大小 II。</p>
<p>当 n = 3，那么我们有 3 个选择：1 或 2 或 3。</p>
<p>假设我们先猜 1，就有两种情况：</p>
<ul>
<li>[猜对]：1 就是正确的数字，所以你支付 0¥，或者</li>
<li>[猜错]：1 不是正确数字，于是你需要支付 1¥（现在，你知道那个正确的数字 &gt; 1，因为每次猜完后你都将被告知猜大了还是猜小了。但就目前的情况来看正确的那个数肯定比 1 大），于是我们得到了一个子问题（2，3）——在[2,3]范围内猜出正确的数字。运用递归，我们可以使用同样的方法解决这个问题，此时你可以选择 2 或 3。如果选择 2，你又有两个可能的结果：2 是正确的数字于是你支付 0¥，或者 2 不是正确的数字那么你支付 2¥ ，现在你知道正确的数字是 3 了（因为只剩下 3 这个数字）。如果选择 3，要么 3 就是正解要么你支付 3¥ 于是你知道 2 才是正确的答案。总结一下，选择 2 最多支付 2¥，选择 3 最多支付 3¥。两相比较，在支付最多的情况下，我们选择那个最小的值（2¥），即数字 2 作为子问题（2，3）的答案。（注意到 minimax 了么~~）所以，最终的花费是 1¥ + 2¥ = 3¥</li>
</ul>
<p>如果你最先猜的是 2，同样会有两个可能的结果：</p>
<ul>
<li>2 是正确的数字，你支付 0¥</li>
<li>2 不是正确的数字，你支付 2¥。此时，你会知道你猜大还是猜小了，于是你马上就知道哪个才是正确答案了。所以，如果你最先猜 2，你最多支付 2¥。</li>
</ul>
<p>同样的，如果你最先猜 3，那么你最多需要花费 4¥。</p>
<p>所以，最先猜 2 才是最优选择，你最多花费 2¥。</p>
<p>参考下面的代码，你会看到这是一个十分自然的递归过程。（使用了二维矩阵缓存结果）</p>
<pre class=" language-java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
  <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span>dp<span class="token punctuation">;</span>

  <span class="token keyword">private</span> <span class="token keyword">int</span> <span class="token function">solve</span><span class="token punctuation">(</span><span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">>=</span> r<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 说明 dp[l][r] 已经被计算过了，直接返回</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>dp<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">[</span>r<span class="token punctuation">]</span> <span class="token operator">!=</span> Integer<span class="token punctuation">.</span>MAX_VALUE<span class="token punctuation">)</span> <span class="token keyword">return</span> dp<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">[</span>r<span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> l<span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> r<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
      dp<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">[</span>r<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">[</span>r<span class="token punctuation">]</span><span class="token punctuation">,</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>i <span class="token operator">+</span> <span class="token function">solve</span><span class="token punctuation">(</span>l<span class="token punctuation">,</span> i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span> i <span class="token operator">+</span> <span class="token function">solve</span><span class="token punctuation">(</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">[</span>r<span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

  <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getMoneyAmount</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    dp <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">int</span><span class="token punctuation">[</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> row <span class="token operator">:</span> dp<span class="token punctuation">)</span>
      Arrays<span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span>row<span class="token punctuation">,</span> Integer<span class="token punctuation">.</span>MAX_VALUE<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token function">solve</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span></code></pre>
<p>我整理一下:<br>最优解结构—-区间[i,j]中的稳赢金额  等于<br>猜i,j中的一个数x后再去猜区间[i,x-1]或者区间[x+1,j]   这会花去 x+MAX(【i,x-1】稳赢金额，【x+1,j】稳赢金额)        </p>
<p> 遍历所有的x情况中,取最小值 即可得到答案</p>
<p>转移方程<br>$$<br>dp[i][j]=\begin{cases}<br>0 &amp; i =j\<br>MIN \big[x+ MAX(dp[i,x-1], dp[x+1,j])\big]   &amp; i&lt;j至少2个数<br>\end{cases}<br>\其中x属于[i,j]中的所有情况<br>$$</p>
<p>举例: 只有两个数</p>
<p>dp[0][1]=MIN(arr[0]+ dp[1][1],  arr[1]+dp[0][0])</p>
<p>dp[0][2]</p>
<p>在这里附上go的递推迭代版本,没有经过优化，而且可读性不如递归调用</p>
<h3 id="实现代码-16"><a href="#实现代码-16" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func getMoneyAmount(n int) int &#123;
    dp := make([][]int, n)
    for i:=0; i&lt;n; i++ &#123;
        dp[i] = make([]int, n)
    &#125;
    // 除去了i==j为0，其他都指为100000标识代价很大
    for i:=0; i&lt;n; i++ &#123;
        for j:=0; j&lt;n; j++ &#123;
            if(i!=j)&#123;
                dp[i][j] = 100000
            &#125;
        &#125;
    &#125;

    for step:=1; step&lt;n;step++ &#123;
        for start:=0;start&lt;n;start++ &#123;
            if(start+step&lt;n) &#123;
                //推出区间为 start 到  start+dp的 稳赢金额,需要遍历区间内每一种情况
                // 因为x现在是下标,当x=0时实际上花费1
                for x:= start; x&lt;=start+step; x++&#123;
                    if(x-1&lt;0) &#123;
                        dp[start][start+step] = min(dp[start][start+step], x+1+ dp[x+1][start+step])
                    &#125;else if(x+1&gt;=n) &#123;
                        dp[start][start+step] = min(dp[start][start+step], x+1+dp[start][x-1])
                    &#125;else&#123;
                        dp[start][start+step] = min(dp[start][start+step], x+1+max(dp[start][x-1], dp[x+1][start+step]))
                    &#125;
                &#125;
            &#125;else&#123;
                break
            &#125;
        &#125;
    &#125;

    return dp[0][n-1]
&#125;

func max(a, b int) int&#123;
    if a&lt;b &#123;
        a=b
    &#125;
    return a
&#125;
func min(a, b int) int&#123;
    if a&gt;b &#123;
        a=b
    &#125;
    return a
&#125;</code></pre><p>附：leetcode  java代码</p>
<pre><code>public class Solution &#123;
    public int getMoneyAmount(int n) &#123;
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 2; len &lt;= n; len++) &#123;
            for (int start = 1; start &lt;= n - len + 1; start++) &#123;
                int minres = Integer.MAX_VALUE;
                for (int piv = start; piv &lt; start + len - 1; piv++) &#123;
                    int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                    minres = Math.min(res, minres);
                &#125;
                dp[start][start + len - 1] = minres;
            &#125;
        &#125;
        return dp[1][n];
    &#125;
&#125;
复杂度分析

作者：LeetCode
链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/cai-shu-zi-da-xiao-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</code></pre><h2 id="376-摆动序列"><a href="#376-摆动序列" class="headerlink" title="376. 摆动序列"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/wiggle-subsequence/">376. 摆动序列</a></h2><h3 id="解题思路-14"><a href="#解题思路-14" class="headerlink" title="解题思路"></a>解题思路</h3><p>最长上升子序列是定义成以第i个数字结尾的最长上升子序列长度</p>
<p>1   3   2   4</p>
<p>长度依次为 1、2、2、3      dp[i+1]= i+1之前的所有满足arr[i+1]&gt;arr[x]的情况dp[x]+1的最大值</p>
<p>最长摆动序列定义成考虑到第i个数字(不一定以第i个数字结尾)  最后差为负的最大长度   以及最后差为正的最大程度两种情况</p>
<p>up[i]和down[i]</p>
<p>以up[i+1]的变化为例  </p>
<p><img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20210112145852.png" alt="image-20210112145844102"></p>
<p>我们知道了arr[i+1]&gt;arr[i]则up[i+1]=down[i]+1,  不论最后下降的两个数字在什么位置</p>
<p>​                  arr[i+1]&lt;=arr[i]则up[i+1]=up[i]不变</p>
<p>对于down也是这样</p>
<p>最后状态转移方程<br>$$<br>up[i+1]=<br>\begin{cases}<br>1 &amp; i=0 \<br>down[i]+1 &amp; arr[i+1]&gt;arr[i]且i&gt;0 \<br>up[i] &amp; arr[i+1]&lt;=arr[i]且i&gt;0<br>\end{cases}<br>\————————-\<br>down[i+1]=<br>\begin{cases}<br>1 &amp; i=0 \<br>up[i]+1 &amp; arr[i+1]&lt;arr[i]且i&gt;0 \<br>down[i] &amp; arr[i+1]&gt;=arr[i]且i&gt;0<br>\end{cases}<br>$$</p>
<p>参考leetcode题解<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/wiggle-subsequence/solution/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/">https://leetcode-cn.com/problems/wiggle-subsequence/solution/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/</a></p>
<p>引用其例图方便理解<img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20210112150610.png" alt="实图"></p>
<h3 id="实现代码-17"><a href="#实现代码-17" class="headerlink" title="实现代码"></a>实现代码</h3><pre><code>func wiggleMaxLength(nums []int) int &#123;
    length := len(nums)
    if(length&lt;=0) &#123;
        return 0
    &#125;
    upDp, downDp := make([]int, length), make([]int, length)
    upDp[0], downDp[0] = 1, 1
    for i:=1; i&lt; length; i++ &#123;
        upDp[i] = upDp[i-1]
        downDp[i] = downDp[i-1]
        if nums[i] &gt; nums[i-1] &#123;
            upDp[i] = downDp[i-1]+1
        &#125;else if nums[i] &lt; nums[i-1] &#123;
            downDp[i] = upDp[i-1]+1
        &#125;
    &#125;
    if upDp[length-1] &gt; downDp[length-1] &#123;
        downDp[length-1] = upDp[length-1]
    &#125;
    return downDp[length-1]

&#125;</code></pre><p>1.为什么会用到动态规划呢？</p>
<p>一个长的摆动序列，逐个截取尾部的元素还是摆动序列</p>
<p>2.如何想到这种要考虑到两个状态转移的思路的呢？</p>
<p>整个题难点在于不是求最长<strong>连续</strong>的摆动序列而是允许删除部分元素</p>
<p>如果是连续的话和最长上升子序列完全是一个思路，但是如果是不连续的怎么做呢？</p>
<p>想法一：</p>
<p>知道一个范围内不连续的最长摆动序列，  我们如何推演出更大范围的最长摆动序列？</p>
<p>推不出来，因为更大范围多出来的一个元素和前一个元素的关系知道，但是也不知道 小范围  最后一个是上升还是下降呀</p>
<p>想法二： 既然不知道小范围是上升下降，那我们将问题状态细分，分成知道 一个范围内    结尾为上升态和下降态 最长摆动序列长度</p>
<p>如果小范围的摆动序列的最后两个数字包括arr[i]也可以吗通过比较arr[i+1]和arr[i]即可区分了，但是如果不包括呢？</p>
<p>想法三：即使不包括arr[i]也不影响？<br>如果不包括arr[i],那上升态摆动序列最后的一个元素一定小于等于arr[i]</p>
<p>3.这道题如果用贪心算法如何求解呢？</p>
<p>每次上升尽可能上升到最大，每次下降尽可能下降到最小，这样维持一个贪心最优的摆动序列，一个一个挨个元素比较，o(n)时间即可解决</p>
<p>吐槽一下leet’code的计算耗时0ms,bug了。。。</p>
<p><img src="https://raw.githubusercontent.com/linxuesong/TyporaPictures/master/img/20210113180725.png" alt="image-20210113180717051"></p>
<h2 id="474-一和零"><a href="#474-一和零" class="headerlink" title="474. 一和零"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/ones-and-zeroes/">474. 一和零</a></h2><h3 id="解题思路-15"><a href="#解题思路-15" class="headerlink" title="解题思路"></a>解题思路</h3><p>题目和01背包问题类似，0-1背包问题如下:</p>
<p>给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。</p>
<p>我们转换一下</p>
<p>给定一组物品，每种物品都有自己的重量（w[i]数组），在限定的总重量内，我们如何选择，才能拿到最多的物品。</p>
<p>dp[i][j]表示考虑前i件物品在容量为j的情况下可以拿到的最多物品数量,对于第i件物品有拿和不拿两种选择<br>$$<br>dp[i][j] =<br>\begin{cases}<br>dp[i-1][j] &amp;j-w[i]&lt;0装不下，只能不拿\<br>max(dp[i-1][j], dp[i-1][j-w[i]]+1) &amp;j-w[i]&gt;=0 装的下，拿或不拿<br>\end{cases}<br>$$<br>引申到我们现在的题目，背包容量变成了0和1的最大数量，其实就是重量变成了两个维度</p>
<p>dp[i][j][k]表示考虑前i件物品在容量为j,k的情况下可以拿到的最多物品数量，对于第i件物品有拿或不拿两种选择</p>
<hr>
<p>$$<br>dp[i][j][k] =<br>\begin{cases}<br>dp[i-1][j][k] &amp;j-arr0[i]&lt;0||k-arr1[i]&lt;0装不下，只能不拿\<br>max(dp[i-1][j][k], dp[i-1][j-arr0[i]][k-arr1[i]]+1) &amp;j-arr0[i]&gt;=0且k-arr1[i]&gt;=0 装的下，拿或不拿<br>\end{cases}<br>$$<br>arr0[i],arr1[i]表示第i个元素的 0和1的数量</p>
<hr>
<h3 id="实现代码-18"><a href="#实现代码-18" class="headerlink" title="实现代码"></a>实现代码</h3><pre class=" language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">findMaxForm</span><span class="token punctuation">(</span>strs <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">,</span> m <span class="token builtin">int</span><span class="token punctuation">,</span> n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    strLen <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">)</span>
    dp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> strLen<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> strLen<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>strLen<span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        zeroCnt<span class="token punctuation">,</span> oneCnt <span class="token operator">:=</span> <span class="token function">zeroAndOneCount</span><span class="token punctuation">(</span>strs<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span> k<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span> j<span class="token operator">>=</span>zeroCnt<span class="token operator">&amp;&amp;</span>k<span class="token operator">>=</span>oneCnt <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">Max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>zeroCnt<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token operator">-</span>oneCnt<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">)</span>
                <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span><span class="token keyword">else</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
                    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> dp<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span>
                <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
            <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>strLen<span class="token punctuation">]</span><span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token punctuation">]</span>
<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

<span class="token keyword">func</span> <span class="token function">zeroAndOneCount</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    zero<span class="token punctuation">,</span> one <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span>
    <span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span> ch <span class="token operator">:=</span> <span class="token keyword">range</span> s <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> ch <span class="token operator">==</span> <span class="token string">'0'</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            zero<span class="token operator">++</span> 
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span><span class="token keyword">else</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
            one<span class="token operator">++</span>
        <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> zero<span class="token punctuation">,</span> one
<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>

<span class="token keyword">func</span> <span class="token function">Max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> a<span class="token operator">></span>b <span class="token operator">&amp;</span>#<span class="token number">123</span><span class="token punctuation">;</span>
        b <span class="token operator">=</span> a
    <span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> b
<span class="token operator">&amp;</span>#<span class="token number">125</span><span class="token punctuation">;</span>
</code></pre>

        </div>
        <!-- .entry-content -->
        <div class="single-reward">
          <div class="reward-open">赏
            <div class="reward-main">
              <ul class="reward-row">
                <li class="alipay-code"><img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/donate/AliPayQR.jpg"></li>
                <li class="wechat-code"><img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/donate/WeChanSQ.jpg"></li>
		<>
              </ul>
            </div>
          </div>
        </div>
        <div style="text-align:center; width: 100%" class="social-share share-mobile" data-disabled="diandian, tencent"></div>
        <footer class="post-footer">
          <div class="post-lincenses"><a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="nofollow"><i class="fa fa-creative-commons" aria-hidden="true"></i> 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议</a></div>
          <div class="post-share">
            <div class="social-share sharehidden share-component"></div>
            <i class="iconfont show-share icon-forward"></i>
          </div>
        </footer><!-- .entry-footer -->
      </article>

<!--对于每一篇发布文章添加标签统计展示-->
          <div class="post-tags">


	<div class="tag-cloud">
                  <div class="tag-cloud-title">
                  </div>
                  <div class="tag-cloud-tags">
                  <a href="/tags/C/" style="font-size: 10px; color: #f38181">C++</a> <a href="/tags/Go/" style="font-size: 10px; color: #f38181">Go</a> <a href="/tags/Golang/" style="font-size: 11.67px; color: #e3918f">Golang</a> <a href="/tags/JAVA/" style="font-size: 15px; color: #c4b1aa">JAVA</a> <a href="/tags/LeetCode/" style="font-size: 16.67px; color: #b4c1b8">LeetCode</a> <a href="/tags/MarkDown/" style="font-size: 10px; color: #f38181">MarkDown</a> <a href="/tags/Reids/" style="font-size: 10px; color: #f38181">Reids</a> <a href="/tags/Sakura/" style="font-size: 13.33px; color: #d4a19c">Sakura</a> <a href="/tags/String/" style="font-size: 10px; color: #f38181">String</a> <a href="/tags/go/" style="font-size: 10px; color: #f38181">go</a> <a href="/tags/golang/" style="font-size: 10px; color: #f38181">golang</a> <a href="/tags/hexo/" style="font-size: 10px; color: #f38181">hexo</a> <a href="/tags/java/" style="font-size: 10px; color: #f38181">java</a> <a href="/tags/linux/" style="font-size: 11.67px; color: #e3918f">linux</a> <a href="/tags/mac%E8%BD%AF%E4%BB%B6/" style="font-size: 10px; color: #f38181">mac软件</a> <a href="/tags/nginx/" style="font-size: 13.33px; color: #d4a19c">nginx</a> <a href="/tags/protobuf/" style="font-size: 10px; color: #f38181">protobuf</a> <a href="/tags/sakura/" style="font-size: 10px; color: #f38181">sakura</a> <a href="/tags/web/" style="font-size: 10px; color: #f38181">web</a> <a href="/tags/%E4%B8%BB%E9%A2%98%E7%BE%8E%E5%8C%96/" style="font-size: 20px; color: #95e1d3">主题美化</a> <a href="/tags/%E5%8C%85%E7%AE%A1%E7%90%86%E5%B7%A5%E5%85%B7/" style="font-size: 10px; color: #f38181">包管理工具</a> <a href="/tags/%E5%8D%9A%E5%AE%A2%E5%BD%92%E7%B1%BB/" style="font-size: 10px; color: #f38181">博客归类</a> <a href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" style="font-size: 10px; color: #f38181">多线程</a> <a href="/tags/%E5%B0%8F%E7%9B%AE%E6%A0%87/" style="font-size: 10px; color: #f38181">小目标</a> <a href="/tags/%E5%BC%82%E5%B8%B8/" style="font-size: 10px; color: #f38181">异常</a> <a href="/tags/%E6%82%A6%E8%AF%BB/" style="font-size: 10px; color: #f38181">悦读</a> <a href="/tags/%E6%84%9F%E6%82%9F/" style="font-size: 10px; color: #f38181">感悟</a> <a href="/tags/%E6%95%B0%E7%BB%84/" style="font-size: 18.33px; color: #a5d1c5">数组</a> <a href="/tags/%E6%96%87%E4%BB%B6%E8%AF%BB%E5%8F%96/" style="font-size: 10px; color: #f38181">文件读取</a> <a href="/tags/%E7%AE%80%E5%8D%95/" style="font-size: 16.67px; color: #b4c1b8">简单</a> <a href="/tags/%E7%AE%97%E6%B3%95/" style="font-size: 11.67px; color: #e3918f">算法</a> <a href="/tags/%E8%B5%84%E6%96%99%E6%95%B4%E7%90%86/" style="font-size: 13.33px; color: #d4a19c">资料整理</a> <a href="/tags/%E8%BD%AF%E4%BB%B6%E5%AE%89%E8%A3%85/" style="font-size: 10px; color: #f38181">软件安装</a> <a href="/tags/%E9%BB%91%E7%A7%91%E6%8A%80/" style="font-size: 10px; color: #f38181">黑科技</a>
                  </div>

                </div>

          </div>
<!--对于每一篇发布文章添加标签统计展示-->
      <!-- #post-## -->
      <div class="toc" style="background: none;"></div>
      <section class="post-squares nextprev">
        
          
            <div class="post-nepre half previous">
          
            <a href="/2020/12/11/%E5%A2%9E%E5%8A%A0%E6%96%87%E7%AB%A0%E8%B4%A1%E7%8C%AE%E6%97%A5%E5%8E%86/" rel="prev">
              <div class="background">
                <img class="lazyload" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/loader/orange.progress-bar-stripe-loader.svg" data-src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/1P421143I2-5-1200.jpg" style="width: 100%; height: 100%; object-fit: cover; pointer-events: none;" onerror="imgError(this,3)" src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/1P421143I2-5-1200.jpg">
              </div>
              <span class="label">
              Previous Post</span>
              <div class="info">
                <h3>
                增加文章贡献日历</h3>
                <hr>
              </div>
            </a>
          </div>
        
        
          
            <div class="post-nepre half next">
          
            <a href="/2020/12/04/hexo%E5%A2%9E%E5%8A%A0RSS%E8%AE%A2%E9%98%85%E5%8A%9F%E8%83%BD/" rel="next">
              <div class="background">
                <img class="lazyload" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/loader/orange.progress-bar-stripe-loader.svg" data-src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/1P421143I2-8-1200.jpg" style="width: 100%; height: 100%; object-fit: cover; pointer-events: none;" onerror="imgError(this,3)" src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/articleCover/动漫女/1P421143I2-8-1200.jpg">
              </div>
              <span class="label">
              Next Post</span>
              <div class="info">
                <h3>
                hexo增加RSS订阅功能</h3>
                <hr>
              </div>
            </a>
          </div>
        
      </section>
      
<div id="vcomments"></div>
<script>
  window.onload = function(){
      var valine = new Valine();
      valine.init({
        el: '#vcomments',
        appId: "RmgA0rMeKIWWIkhSTpqhV4oG-gzGzoHsz",
        appKey: "iwivlkfT6bGJRQS74SaKYjal",
        path: window.location.pathname,
        placeholder: "你是我一生只会遇见一次的惊喜 ..."
      })
  }
</script>

      <section class="author-profile">
        <div class="info" itemprop="author" itemscope="" itemtype="https://schema.org/Person">
          <a href="linxuesong.github.io" class="profile gravatar"><img src="https://wx1.sinaimg.cn/large/006bYVyvgy1ftand2qurdj303c03cdfv.jpg" itemprop="image" alt="linxuesong" height="70" width="70"></a>
          <div class="meta">
            <span class="title">Author</span>
            <h3 itemprop="name">
            <a href="linxuesong.github.io" itemprop="url" rel="author">linxuesong</a>
            </h3>
          </div>
        </div>
        <hr>
        <p><i class="iconfont icon-write"></i>一个好奇的人</p>
      </section>
    </main><!-- #main -->
  </div><!-- #primary -->
</div>



    </div>

    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="Type something..."/>
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: 'Posts',
            // PAGES: 'Pages',
            CATEGORIES: 'Categories',
            TAGS: 'Tags',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

    <!-- <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2021 John Doe<br>
      powered_by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer> -->
<footer id="colophon" class="site-footer" role="contentinfo">
  <div class="site-info">
    <div class="footertext">
      <div class="img-preload">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/wordpress-rotating-ball-o.svg">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/disqus-preloader.svg">
      </div>
      <p style="color: #666666;">&copy 2018</p>
    </div>
	<!-- 网站数据统计 -->
        <div class="footer-device">
          <p style="font-family: 'Ubuntu', sans-serif;">
            <span style="color: #ff9999;padding-left: 20px;">
                <!-- 网站运行时间统计 -->
                <i class="fa fa-clock-o" aria-hidden="true"></i>
                <span id="time" align="center">载入时间中...</span>
                <script>
                var now = new Date(); 
                function createtime() { 
                      var grt= new Date("12/12/2018");//在此处修改你的建站时间
                      now.setTime(now.getTime()+250); 
                      days = (now - grt ) / 1000 / 60 / 60 / 24; dnum = Math.floor(days); 
                      hours = (now - grt ) / 1000 / 60 / 60 - (24 * dnum); hnum = Math.floor(hours); 
                      if(String(hnum).length ==1 ){hnum = "0" + hnum;} minutes = (now - grt ) / 1000 /60 - (24 * 60 * dnum) - (60 * hnum); 
                      mnum = Math.floor(minutes); if(String(mnum).length ==1 ){mnum = "0" + mnum;} 
                      seconds = (now - grt ) / 1000 - (24 * 60 * 60 * dnum) - (60 * 60 * hnum) - (60 * mnum); 
                      snum = Math.round(seconds); if(String(snum).length ==1 ){snum = "0" + snum;} 
                      document.getElementById("time").innerHTML = "小破站在各种灾难中苟活了 "+ dnum +" 天 "+hnum + " 小时 " + mnum + " 分 " + snum + " 秒";      
                  } 
                  setInterval("createtime()",250);
                </script>
            </span> 
          </p>
        </div>
        <div class="footer-device">
          <p style="font-family: 'Ubuntu', sans-serif;">
            <span style="color: #b9b9b9;padding-left: 20px;">
              <!-- 全网站字数统计wordcount -->
              <i class="fa fa-line-chart"  aria-hidden="true" style="color: #ff9999;display:inline-block"></i> 博客全站共: <span class="post-count" style="color:#ff9999;">59.9k</span>字</span>
              <!-- 不蒜子网页计数器 -->
              
              <span style="padding-left: 20px;"><i class="fa fa-fire" aria-hidden="true" style="color: #ff9999;display:inline-block"></i><span id="busuanzi_container_site_pv">总访问量： <span id="busuanzi_value_site_pv" style="color:#ff9999;"></span>次</span>
              </span>
              
              
              <span style="padding-left: 20px;"><i class="fa fa-user" aria-hidden="true" style="color: #ff9999;display:inline-block"></i><span id="busuanzi_container_site_uv">总访问人数： <span id="busuanzi_value_site_uv" style="color:#ff9999;"></span>人</span>
              </span>
              
            </span>
          </p>
        </div>
    <div class="footer-device">
    <p style="font-family: 'Ubuntu', sans-serif;">
        <span style="color: #b9b9b9;">Theme <a href="https://github.com/honjun/hexo-theme-sakura" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Sakura</a> <i class="iconfont icon-sakura rotating" style="color: #ffc0cb;display:inline-block"></i> by <a href="https://2heng.xin/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Mashiro</a>&<a href="https://www.hojun.cn/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Hojun</a>, Powered by Hexo, Hosted by Coding Pages</a>
        </span>
      </p>
    </div>
  </div><!-- .site-info -->
</footer>

<!-- 指定网页去除网页底部footer的网站信息 -->
<!--  切换页面后需要再显示出来 -->
<!--
<script>
    var url = document.URL.toString();
    var reg = new RegExp("sourceshare");
    var obj = document.getElementById("colophon");
    if(url.match(reg)){
        obj.style.display="none";
    }else {
        obj.style.display="block";
    }
</script>
-->
<!-- <script src="/js/tocbot.js"></script> -->
<script type="text/javascript" src="/js/lib.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script type="text/javascript" src="/js/InsightSearch.js"></script>
<script type="text/javascript" src="/js/jquery.fancybox.min.js"></script>
<script type="text/javascript" src="/js/zoom.min.js"></script>
<script type="text/javascript" src="/js/sakura-app.js"></script>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='//unpkg.com/valine@1.3.4/dist/Valine.min.js'></script>
<script src="/js/botui.js"></script>
<!-- 不蒜子 网页计数器 -->
<script src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<!-- <script src="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.min.js"></script> -->
<script type="text/javascript">
/* <![CDATA[ */
if (/Android|webOS|iPhone|iPod|BlackBerry/i.test(navigator.userAgent)) {
  var Poi = {"pjax":"1","movies":{"url": "https://cdn.jsdelivr.net/gh/honjun/hojun@1.2","name":"Unbroken.mp4","live":"close"},"windowheight":"fixed","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
} else {
  var Poi = {"pjax":"1","movies":{"url": "https://cdn.jsdelivr.net/gh/honjun/hojun@1.2","name":"Unbroken.mp4","live":"open"},"windowheight":"auto","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
}
/* ]]> */
</script>
<script>
$(document).ready(function() {
  if ($(".toc").length > 0 && document.body.clientWidth > 1200) {
    if ($(".pattern-center").length > 0) { //有图的情况
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -400,
          scrollSmoothOffset: -85
      });
    } else {
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -85,
          scrollSmoothOffset: -85
      });
    }
    var offsetTop = $('.toc').offset().top - 95;
    window.onscroll = function() {
      var scrollTop = window.pageYOffset || document.documentElement.scrollTop || document.body.scrollTop;
      if (scrollTop >= offsetTop) {
        $('.toc').addClass('toc-fixed');
      } else {
        $('.toc').removeClass('toc-fixed');
      }
    }
  }
});
</script>


  <script>
  (function(i,s,o,g,r,a,m){i["DaoVoiceObject"]=r;i[r]=i[r]||function(){(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;a.charset="utf-8";m.parentNode.insertBefore(a,m)})(window,document,"script",('https:' == document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/7e5676fe.js","daovoice");
    daovoice('init', {
      app_id: "7e5676fe"
    });
    daovoice('update');
  </script>
 



    <div class="openNav no-select" style="height: 50px;">
      <div class="iconflat no-select" style="width: 50px; height: 50px;">
        <div class="icon"></div>
      </div>
      <div class="site-branding search-form-submit">
        <i class="iconfont js-toggle-search iconsearch icon-search"></i>
      </div>
    </div>
  </section>
  <div id="mo-nav" class="">
  <div class="m-avatar">
    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/avatar.jpg">
  </div>
  <p style="text-align: center; color: #333; font-weight: 900; font-family: 'Ubuntu', sans-serif; letter-spacing: 1.5px">楓の葉lean</p>
  <p style="text-align: center; word-spacing: 20px;">
    
      
        <a href="http://github.com/honjun" class="fa fa-github" target="_blank" style="color: #333; margin-left:20px"></a>
      
        <a href="http://weibo.com/mashirozx?is_all=1" class="fa fa-weibo" target="_blank" style="color: #dd4b39; margin-left:20px"></a>
      
        <a href="https://wpa.qq.com/msgrd?v=3&uin=954655431&site=qq&menu=yes" class="fa fa-qq" target="_blank" style="color: #25c6fe; margin-left:20px"></a>
      
    
  </p>
  <ul id="menu-new-1" class="menu">
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
            首页
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
            归档
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/categories/%E6%8A%80%E6%9C%AF/">
                  <i class="fa fa-laptop" aria-hidden="true"></i>
                  技术
                </a>
              </li>
            
              <li>
                <a href="/categories/%E7%94%9F%E6%B4%BB/">
                  <i class="fa fa-file-text-o" aria-hidden="true"></i>
                  生活
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%B5%84%E6%BA%90/">
                  <i class="fa fa-cloud-download" aria-hidden="true"></i>
                  资源
                </a>
              </li>
            
              <li>
                <a href="/categories/%E9%9A%8F%E6%83%B3/">
                  <i class="fa fa-commenting-o" aria-hidden="true"></i>
                  随想
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                  <i class="fa fa-book" aria-hidden="true"></i>
                  转载
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-area-chart faa-vertical" aria-hidden="true"></i>
            文章统计
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/analytics/">
                  <i class="fa fa-area-chart" aria-hidden="true"></i>
                  统计
                </a>
              </li>
            
              <li>
                <a href="/archives/">
                  <i class="fa fa-calendar" aria-hidden="true"></i>
                  日历
                </a>
              </li>
            
              <li>
                <a href="/tags/">
                  <i class="fa fa-tag" aria-hidden="true"></i>
                  标签
                </a>
              </li>
            
              <li>
                <a href="/categories/">
                  <i class="fa fa-bookmark" aria-hidden="true"></i>
                  分类
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
            清单
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/books/">
                  <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                  书单
                </a>
              </li>
            
              <li>
                <a href="/bangumi/">
                  <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                  番组
                </a>
              </li>
            
              <li>
                <a href="/music/">
                  <i class="fa fa-headphones" aria-hidden="true"></i>
                  歌单
                </a>
              </li>
            
              <li>
                <a href="/movies/">
                  <i class="fa fa-video-camera" aria-hidden="true"></i>
                  电影
                </a>
              </li>
            
              <li>
                <a href="/games/">
                  <i class="fa fa-gamepad" aria-hidden="true"></i>
                  游戏
                </a>
              </li>
            
              <li>
                <a href="/gallery/">
                  <i class="fa fa-photo" aria-hidden="true"></i>
                  图集
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/comment/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
            留言板
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
            友人帐
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/links/">
                  <i class="fa fa-handshake-o" aria-hidden="true"></i>
                  小伙伴
                </a>
              </li>
            
              <li>
                <a href="/friendlink_status/">
                  <i class="fa fa-heartbeat faa-shake" aria-hidden="true"></i>
                  健康值
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/donate/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
            赞赏
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
            关于
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/sourceshare/">
                  <i class="fa fa-share-alt faa-vertical" aria-hidden="true"></i>
                  分享
                </a>
              </li>
            
              <li>
                <a href="/sitelog/">
                  <i class="fa fa-calculator" aria-hidden="true"></i>
                  建站史
                </a>
              </li>
            
              <li>
                <a href="/todolist">
                  <i class="fa fa-tasks" aria-hidden="true"></i>
                  任务书
                </a>
              </li>
            
              <li>
                <a href="/about/">
                  <i class="fa fa-meetup" aria-hidden="true"></i>
                  我？
                </a>
              </li>
            
              <li>
                <a href="/theme-sakura/">
                  <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                  主题
                </a>
              </li>
            
              <li>
                <a href="/lab/">
                  <i class="fa fa-cogs" aria-hidden="true"></i>
                  Lab
                </a>
              </li>
            
              <li>
                <a href="/dinoswords">
                  <i class="fa fa-coffee" aria-hidden="true"></i>
                  娱乐
                </a>
              </li>
            
              <li>
                <a href="/client/">
                  <i class="fa fa-android faa-vertical" aria-hidden="true"></i>
                  客户端
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/atom.xml">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
            RSS
          </span>
        </a>
        
      </li>
    
  </ul>
  <p style="text-align: center; font-size: 13px; color: #b9b9b9;">&copy 2019 hexo-sakura</p>
</div>
<button onclick="topFunction()" class="mobile-cd-top" id="moblieGoTop" title="Go to top" style="display: none;"><i class="fa fa-chevron-up" aria-hidden="true"></i></button>
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css">
<script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script>
<!-- require MetingJS -->
<script src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>
<style>
  .aplayer .aplayer-lrc {
    height: 35px;
  }
  .aplayer .aplayer-lrc p{
    font-size: 16px;
    font-weight: 700;
    line-height: 18px !important;
  }
  .aplayer .aplayer-lrc p.aplayer-lrc-current{
    color: #FF1493;
  }
  .aplayer.aplayer-narrow .aplayer-body{
    left: -66px !important;
  }
  .aplayer.aplayer-fixed .aplayer-lrc {
    display: none;
  }
  .aplayer .aplayer-lrc.aplayer-lrc-hide {
      display:none !important;
  }
  .aplayer.aplayer-fixed .lrc-show {
    display: block;
    background: rgba(255, 255, 255, 0.8);
  }
</style>
<meting-js

</meting-js>
<script>
  $(function(){
    $('body').on('click', '.aplayer', function(){
      if($('.aplayer-button').hasClass('aplayer-play')) {
        $('.aplayer-lrc').removeClass('lrc-show');
      } else {
        $('.aplayer-lrc').addClass('lrc-show');
      }
    })
  });
</script>
  
    <!--1.界面画板娘-->
    <!-- github仓库链接:https://github.com/stevenjoezhang/live2d-widget-->
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css"> 
    <!-- 这条在sakura中已有，可不添加 -->
    <script src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/live2d_qianduan/live2d-widget-master/autoload.js"></script>
    <!--2.樱花飘落背景-->
    <!--
    <script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/sakura.js"></script>  
    -->
    <!--3.鼠标移动特效（暂时关闭）-->
    <!--
    <script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/xuehua.js"></script>
    -->
    <!--4.图片预加载-->
    <script src="//instant.page/3.0.0" type="module" defer integrity="sha384-OeDn4XE77tdHo8pGtE1apMPmAipjoxUQ++eeJa6EtJCfHlvijigWiJpD7VDPWXV1"></script>
    <!--5.鼠标点击爆炸特效-->
    <script type="text/javascript" src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/js/鼠标特效/鼠标点击爆炸烟花特效JS/meme.js"></script>
    <canvas class="fireworks" style="position:fixed;left:0;top:0;z-index:99999999;pointer-events:none;"></canvas>
    <script type="text/javascript" src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/js/鼠标特效/鼠标点击爆炸烟花特效JS/anime.min.js"></script>
    <script type="text/javascript" src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/js/鼠标特效/鼠标点击爆炸烟花特效JS/fireworks.js"></script> 
    <!--6.明月浩空音乐播放器插件   下面是盗版(歌单比较全)    还有  正版体验版(只有一个歌单加广告)  也可以用注册版(有后台查看系统) 已绑定qq账号1011572950-->
    <!--这个是盗版的-->
    <!--<script src="https://player.lmih.cn/player/js/player.js" id="myhk" key="demo" m="1"></script>-->
    <!--这个是正版的-->
    <script src="https://myhkw.cn/player/js/player.js" id="myhk" key="160897544983" m="1"></script>
    <!-- 7.主题背景换肤功能 -->
    <div class="skin-menu no-select" id="mainskin" style="position: fixed">
 <div class="theme-controls row-container">
  <ul class="menu-list">
   <li id="white-bg"> <i class="fa fa-television" aria-hidden="true"></i></li>
   <li id="sakura-bg"> <i class="iconfont icon-sakura"></i></li>
   <li id="gribs-bg"> <i class="fa fa-slack" aria-hidden="true"></i></li>
   <li id="KAdots-bg"> <i class="iconfont icon-dots"></i></li>
   <li id="totem-bg"> <i class="fa fa-optin-monster" aria-hidden="true"></i></li>
   <li id="pixiv-bg"> <i class="iconfont icon-pixiv"></i></li>
   <li id="bing-bg"> <i class="iconfont icon-bing"></i></li>
   <li id="dark-bg"> <i class="fa fa-moon-o" aria-hidden="true"></i></li>
  </ul>
 </div>
</div>
<canvas id="night-mode-cover"></canvas>
 
    <div class="changeSkin-gear no-select">
  <div class="keys" id="setbtn"> 
   <span id="open-skinMenu"> 点我试试 | SCHEME TOOL  
     <i class="iconfont icon-gear inline-block rotating"></i> 
   </span>
  </div>
</div>

    <div id="mo-nav" class="">
  <div class="m-avatar">
    <img src="https://cdn.jsdelivr.net/gh/linxuesong/cdn/img/avatar.jpg">
  </div>
  <p style="text-align: center; color: #333; font-weight: 900; font-family: 'Ubuntu', sans-serif; letter-spacing: 1.5px">楓の葉lean</p>
  <p style="text-align: center; word-spacing: 20px;">
    
      
        <a href="http://github.com/honjun" class="fa fa-github" target="_blank" style="color: #333; margin-left:20px"></a>
      
        <a href="http://weibo.com/mashirozx?is_all=1" class="fa fa-weibo" target="_blank" style="color: #dd4b39; margin-left:20px"></a>
      
        <a href="https://wpa.qq.com/msgrd?v=3&uin=954655431&site=qq&menu=yes" class="fa fa-qq" target="_blank" style="color: #25c6fe; margin-left:20px"></a>
      
    
  </p>
  <ul id="menu-new-1" class="menu">
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
            首页
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
            归档
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/categories/%E6%8A%80%E6%9C%AF/">
                  <i class="fa fa-laptop" aria-hidden="true"></i>
                  技术
                </a>
              </li>
            
              <li>
                <a href="/categories/%E7%94%9F%E6%B4%BB/">
                  <i class="fa fa-file-text-o" aria-hidden="true"></i>
                  生活
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%B5%84%E6%BA%90/">
                  <i class="fa fa-cloud-download" aria-hidden="true"></i>
                  资源
                </a>
              </li>
            
              <li>
                <a href="/categories/%E9%9A%8F%E6%83%B3/">
                  <i class="fa fa-commenting-o" aria-hidden="true"></i>
                  随想
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                  <i class="fa fa-book" aria-hidden="true"></i>
                  转载
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-area-chart faa-vertical" aria-hidden="true"></i>
            文章统计
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/analytics/">
                  <i class="fa fa-area-chart" aria-hidden="true"></i>
                  统计
                </a>
              </li>
            
              <li>
                <a href="/archives/">
                  <i class="fa fa-calendar" aria-hidden="true"></i>
                  日历
                </a>
              </li>
            
              <li>
                <a href="/tags/">
                  <i class="fa fa-tag" aria-hidden="true"></i>
                  标签
                </a>
              </li>
            
              <li>
                <a href="/categories/">
                  <i class="fa fa-bookmark" aria-hidden="true"></i>
                  分类
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
            清单
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/books/">
                  <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                  书单
                </a>
              </li>
            
              <li>
                <a href="/bangumi/">
                  <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                  番组
                </a>
              </li>
            
              <li>
                <a href="/music/">
                  <i class="fa fa-headphones" aria-hidden="true"></i>
                  歌单
                </a>
              </li>
            
              <li>
                <a href="/movies/">
                  <i class="fa fa-video-camera" aria-hidden="true"></i>
                  电影
                </a>
              </li>
            
              <li>
                <a href="/games/">
                  <i class="fa fa-gamepad" aria-hidden="true"></i>
                  游戏
                </a>
              </li>
            
              <li>
                <a href="/gallery/">
                  <i class="fa fa-photo" aria-hidden="true"></i>
                  图集
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/comment/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
            留言板
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
            友人帐
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/links/">
                  <i class="fa fa-handshake-o" aria-hidden="true"></i>
                  小伙伴
                </a>
              </li>
            
              <li>
                <a href="/friendlink_status/">
                  <i class="fa fa-heartbeat faa-shake" aria-hidden="true"></i>
                  健康值
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/donate/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
            赞赏
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
            关于
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/sourceshare/">
                  <i class="fa fa-share-alt faa-vertical" aria-hidden="true"></i>
                  分享
                </a>
              </li>
            
              <li>
                <a href="/sitelog/">
                  <i class="fa fa-calculator" aria-hidden="true"></i>
                  建站史
                </a>
              </li>
            
              <li>
                <a href="/todolist">
                  <i class="fa fa-tasks" aria-hidden="true"></i>
                  任务书
                </a>
              </li>
            
              <li>
                <a href="/about/">
                  <i class="fa fa-meetup" aria-hidden="true"></i>
                  我？
                </a>
              </li>
            
              <li>
                <a href="/theme-sakura/">
                  <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                  主题
                </a>
              </li>
            
              <li>
                <a href="/lab/">
                  <i class="fa fa-cogs" aria-hidden="true"></i>
                  Lab
                </a>
              </li>
            
              <li>
                <a href="/dinoswords">
                  <i class="fa fa-coffee" aria-hidden="true"></i>
                  娱乐
                </a>
              </li>
            
              <li>
                <a href="/client/">
                  <i class="fa fa-android faa-vertical" aria-hidden="true"></i>
                  客户端
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/atom.xml">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
            RSS
          </span>
        </a>
        
      </li>
    
  </ul>
  <p style="text-align: center; font-size: 13px; color: #b9b9b9;">&copy 2019 hexo-sakura</p>
</div>
<button onclick="topFunction()" class="mobile-cd-top" id="moblieGoTop" title="Go to top" style="display: none;"><i class="fa fa-chevron-up" aria-hidden="true"></i></button>
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css">
<script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script>
<!-- require MetingJS -->
<script src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>
<style>
  .aplayer .aplayer-lrc {
    height: 35px;
  }
  .aplayer .aplayer-lrc p{
    font-size: 16px;
    font-weight: 700;
    line-height: 18px !important;
  }
  .aplayer .aplayer-lrc p.aplayer-lrc-current{
    color: #FF1493;
  }
  .aplayer.aplayer-narrow .aplayer-body{
    left: -66px !important;
  }
  .aplayer.aplayer-fixed .aplayer-lrc {
    display: none;
  }
  .aplayer .aplayer-lrc.aplayer-lrc-hide {
      display:none !important;
  }
  .aplayer.aplayer-fixed .lrc-show {
    display: block;
    background: rgba(255, 255, 255, 0.8);
  }
</style>
<meting-js

</meting-js>
<script>
  $(function(){
    $('body').on('click', '.aplayer', function(){
      if($('.aplayer-button').hasClass('aplayer-play')) {
        $('.aplayer-lrc').removeClass('lrc-show');
      } else {
        $('.aplayer-lrc').addClass('lrc-show');
      }
    })
  });
</script> 

	
	

	
	
    <!-- 8.增加红灯笼按钮-->
    <!--深夜模式按钮-->
	<a onclick="switchNightMode()" id="sma"> 
		<i class="fa fa-moon-o" id="nightMode" aria-hidden="true"></i> 
	</a>
    <!--圣诞模式按钮-->  
	<script>
		if (localStorage.getItem('themechris') === '1') {
			document.body.classList.add('themechris');
		}
		else if (matchMedia('(prefers-color-scheme: themechris)').matches) {
			document.body.classList.add('themechris');
		}
	</script>
	<a onclick="switchChrisThemes()" id="switchchristmas">
		<img class="theme-buttonchrismas" src="https://hesifan.top/medias/christmas-img/ball.jpg" title="圣诞模式">
	</a>
    <!--春节模式按钮-->  
	<script>
		if (localStorage.getItem('themespring') === '1') {
			document.body.classList.add('themespring');
		}
		else if (matchMedia('(prefers-color-scheme: themespring)').matches) {
			document.body.classList.add('themespring');
		}
	</script>
    <div onclick="switchSpringThemes()" id="switchspring">
        <img class="theme-button" src="https://hesifan.top/medias/spring-img/denglong.png" title="春节模式">
    </div>
  
    <!--春节主题的大红灯笼-->
        <div class="denglong">
        <div class="deng-box">
            <div class="deng">
                <div class="xian"></div>
                <div class="deng-a">
                    <div class="deng-b"><div class="deng-t">喜迎</div></div>
                </div>
                <div class="shui shui-a"><div class="shui-c"></div><div class="shui-b"></div></div>
            </div>
        </div>
        <div class="deng-box1">
            <div class="deng">
                <div class="xian"></div>
                <div class="deng-a">
                    <div class="deng-b"><div class="deng-t">元旦</div></div>
                </div>
                <div class="shui shui-a"><div class="shui-c"></div><div class="shui-b"></div></div>
            </div>
        </div>
    </div>
	<!--春节主题大红灯笼-->
    <!--可以在你想要展示小挂件的地方加上这个挂件，还没有完善等之后再进行吧-->
    <!--圣诞主题小挂件-->
	<div class="caishendengsd">        
		<div class="caishenxiansd">
			<img class="caishenpicsd" src="https://hesifan.top/medias/christmas-img/2.png">
		</div>              
	</div>
    <!-圣诞主题小挂件结束-->
	<!--春节主题小挂件-->
	<div class="caishendeng">        
		<div class="caishenxianleft">
			<img class="caishenpic fudai" src="https://hesifan.top/medias/spring-img/3.png">
		</div>            
	</div>
	<!-春节主题小挂件结束-->
       <script>
	   // 切换深色模式JS
	   function switchNightMode() {
			var body = document.body; 
			if(body.classList.contains('dark')){ 
				document.body.classList.remove('dark'); 
				localStorage.setItem('dark','0'); 
				$('#nightMode').removeClass("fa-lightbulb-o").addClass("fa-moon-o"); 
				return; 
			} else {
				document.body.classList.add('dark'); 
				localStorage.setItem('dark','1'); 
				$('#nightMode').removeClass("fa-moon-o").addClass("fa-lightbulb-o"); 
				return; 
			} 
	   }
	       // 中国节日按钮切换
	
    function switchSpringThemes() {
        var body = document.body;
        if(body.classList.contains('themechris')){
            document.body.classList.remove('themechris');
            localStorage.setItem('themechris','0');
            document.body.classList.add('themespring');
            localStorage.setItem('themespring','1');
            return;
        }
        if(body.classList.contains('themespring')){
        document.body.classList.remove('themespring');
        localStorage.setItem('themespring','0');
        return;
        } else {
        document.body.classList.add('themespring');
        localStorage.setItem('themespring','1');
		
        return;
        }
    };

    // 圣诞节按钮切换
    function switchChrisThemes() {
        var body = document.body;
        if(body.classList.contains('themespring')){
            document.body.classList.remove('themespring');
            localStorage.setItem('themespring','0');
            document.body.classList.add('themechris');
            localStorage.setItem('themechris','1');
            return;
        }
        if(body.classList.contains('themechris')){
        document.body.classList.remove('themechris');
        localStorage.setItem('themechris','0');
        return;
        } else {
        document.body.classList.add('themechris');
        localStorage.setItem('themechris','1');
        return;
        }
    };
	</script>
</body>
</html>
